二楼贴代码。
```cpp
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline void chkmax(T&a, T b) { a = a > b ? a : b; }
template<typename T> inline T Max(T a, T b) { return a > b ? a : b; }
namespace Data_Maker {
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 srand(unsigned x) {
using namespace Data_Maker;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;
}
int read() {
using namespace Data_Maker;
int a = rand_() & 32767;
int b = rand_() & 32767;
return a * 32768 + b;
}
typedef unsigned long long ull;
const int MAXN = 20000010;
const int SZ = 10010;
const int SQ = 2010;
ull res;
int a[MAXN];
int Mx[SQ][SQ];
int pre[MAXN];
int bck[MAXN];
struct Node {
int L, R, S;
}s[SQ];
int main() {
int n, m;
unsigned sr; cin >> n >> m >> sr; int sz = 0, sq = 1; srand(sr);
for(int i = 1; i <= n; i++) a[i] = pre[i] = bck[i] = read();
for(int i = 1; i <= n; i++) {
++sz, chkmax(Mx[sq][sq], a[i]);
if(sz == 1) s[sq].L = i; s[sq].R = i;
if(sz == 10000) s[sq].S = sz, sz = 0, ++sq;
} s[sq].S = sz, sq -= !sz;
for(int i = 1; i <= sq; i++)
for(int j = i + 1; j <= sq; j++)
Mx[i][j] = Max(Mx[i][j - 1], Mx[j][j]);
for(int i = 2; i <= n; i++)
if(i % 10000 != 1)
chkmax(pre[i], pre[i - 1]);
for(int i = n - 1; i; i--)
if(i % 10000 != 0)
chkmax(bck[i], bck[i + 1]);
while(m--) {
int l = read() % n + 1, r = read() % n + 1, t;
if(l > r) t = l, l = r, r = t;
int ans = 0, pL = (l + 9999) / 10000, pR = (r + 9999) / 10000;
if(pL < pR - 1) chkmax(ans, Mx[pL + 1][pR - 1]);
if(pL != pR) chkmax(ans, bck[l]), chkmax(ans, pre[r]);
else for(int i = l; i <= r; i++) chkmax(ans, a[i]);
// for(int i = l; i <= r; i++) chkmax(ans, a[i]);
res += ans;
}
cout << res << endl;
return res;
}
```
by CYJian @ 2019-10-12 23:24:02
~~我本地跑这代码也是 RE 啊~~
by Kewth @ 2019-10-13 14:38:12
~~好吧没什么是我数据输错了~~
by Kewth @ 2019-10-13 14:39:39
我知道了你 main 函数 return 了 res 啊。。。
by Kewth @ 2019-10-13 14:41:16
kg
by S0CRiA @ 2021-02-16 20:11:31
kg
by Yusani_huh @ 2021-04-03 08:41:38
kg
by wangjiayuan @ 2023-08-17 22:24:27