lxl ST表
然后就愉悦地~
#include <bits/stdc++.h>
using namespace std;
#define get(x) (((x) + 63) >> 6)
typedef unsigned uint;
const int maxn = 2e7 + 10;
int n, m, K, tot, a[maxn], lef[maxn], rig[maxn], lg[maxn >> 6], val[20][maxn >> 6];
namespace GenHelper {
uint z1, z2, z3, z4, b;
inline uint rnd() {
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);
}
}
inline void srand(uint x) {
using namespace GenHelper;
z1 = x;
z2 = (~x) ^ 0x233333333u;
z3 = x ^ 0x1234598766u;
z4 = (~x) + 51;
}
inline int read() {
using namespace GenHelper;
int a = rnd() & 32767;
int b = rnd() & 32767;
return a << 15 | b;
}
inline int query(int l, int r) {
if (l > r) return 0;
int tmp = lg[r - l + 1];
return max(val[tmp][l], val[tmp][r - (1 << tmp) + 1]);
}
int main() {
scanf("%d %d %d", &n, &m, &K);
srand(K);
for (int i = 1; i <= n; ++i) {
a[i] = read();
val[0][get(i)] = max(a[i], val[0][get(i)]);
}
tot = get(n);
for (int i = 2; i <= tot; ++i) {
lg[i] = lg[i >> 1] + 1;
}
for (int i = 1, lst = 0; i <= n; ++i) {
lef[i] = lst = max(a[i], lst);
if (!(i & 63)) lst = 0;
}
for (int i = n, lst = 0; i; --i) {
if (!(i & 63)) lst = 0;
rig[i] = lst = max(a[i], lst);
}
for (int i = 1; i < 21; ++i) {
for (int j = 1; j + (1 << i) - 1 <= tot; ++j) {
val[i][j] = max(val[i - 1][j], val[i - 1][j + (1 << (i - 1))]);
}
}
unsigned long long ans = 0;
for (int q = 1, l, r, L, R, res; q <= m; ++q) {
l = read() % n + 1;
r = read() % n + 1;
if (l > r) l ^= r ^= l ^= r;
L = get(l), R = get(r), res = 0;
if (L == R) {
for (int i = l; i <= r; ++i) {
res = max(res, a[i]);
}
} else {
res = max(max(rig[l], lef[r]), query(L + 1, R - 1));
}
ans += res;
}
printf("%llu", ans);
return 0;
}