@[5k_sync_closer](/user/388651)
by sto_5k_orz @ 2023-08-04 12:06:06
@[5k_sync_closer](/user/388651)
by sto_5k_orz @ 2023-08-04 14:18:18
@[Stitch0711](/user/675466) 考虑 $l,r$ 在相邻块的情况
by 5k_sync_closer @ 2023-08-04 14:22:20
@[5k_sync_closer](/user/388651) 考虑了
by sto_5k_orz @ 2023-08-04 14:25:00
ask 里面 $l>r$ 就是在相邻块的吧
by sto_5k_orz @ 2023-08-04 14:26:28
@[5k_sync_closer](/user/388651) 但是如果没有考虑的话直接保龄了捏
by sto_5k_orz @ 2023-08-04 14:38:44
@[Stitch0711](/user/675466) 过了
```cpp
#include<bits/stdc++.h>
using namespace std;
namespace GenHelper
{
unsigned z1,z2,z3,z4,b;
unsigned rand_()
{
b=((z1<<6)^z1)>>13;
z1=((z1&4294967294U)<<18)^b;
b=((z2<<2)^z2)>>27;
z2=((z2&4294967288U)<<2)^b;
b=((z3<<13)^z3)>>21;
z3=((z3&4294967280U)<<7)^b;
b=((z4<<3)^z4)>>12;
z4=((z4&4294967168U)<<13)^b;
return (z1^z2^z3^z4);
}
}
void ssrand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
using namespace GenHelper;
int a=rand_()&32767;
int b=rand_()&32767;
return a*32768+b;
}
const int N = 2e7 + 10;
int dp[N / 500 + 5][16], le[N / 500 + 5], ri[N / 500 + 5], in[N], a[N], mx[N / 500 + 5], tot, pre[N], suf[N];
int ask(int l, int r) {
if(l > r) return 0; int k = __lg(r - l + 1);
return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}
signed main() {
int n, q, s; cin >> n >> q >> s; ssrand(s); unsigned long long ans = 0;
for(int i = 1; i <= n; i++) a[i] = read(); int B = 500;
for(int i = 1; i <= n; i++) in[i] = (i + B - 1) / B;
for(int i = 1; i <= n; i++) {
int M = a[i];
int j = i; while(j < n && in[j + 1] == in[i]) j++, M = max(M, a[j]);
++tot; le[tot] = i, ri[tot] = j; mx[tot] = M; suf[ri[tot]] = a[ri[tot]]; pre[le[tot]] = a[le[tot]];
for(int k = le[tot] + 1; k <= ri[tot]; k++) pre[k] = max(pre[k - 1], a[k]);
for(int k = ri[tot] - 1; k >= le[tot]; k--) suf[k] = max(suf[k + 1], a[k]);
i = j;
}
for(int i = 1; i <= tot; i++) dp[i][0] = mx[i];
for(int j = 1; j < 16; j++) for(int i = 1; i + (1 << j) - 1 <= tot; i++) dp[i][j] = max(dp[i][j - 1], dp[i + (1 << j - 1)][j - 1]);
while(q--) {
int l = read() % n + 1, r = read() % n + 1; if(l > r) swap(l, r);
if(in[l] == in[r]) {int mx = 0; for(int i = l; i <= r; i++) mx = max(mx, a[i]); ans += mx; continue;}
ans += max(ask(in[l] + 1, in[r] - 1), max(suf[l], pre[r]));
}
cout << ans;
return 0;
}
```
by 5k_sync_closer @ 2023-08-04 15:13:50
@[5k_sync_closer](/user/388651) 是不是就改了个 $i=j$
by sto_5k_orz @ 2023-08-04 15:23:40
% 5k
by sto_5k_orz @ 2023-08-04 15:24:15