线段树救爷爷。
回复评论：这不是 zkw 线段树，有根本性差异。哪怕是根据 zkw PPT 中提到的核心要素，也对不上。
https://www.luogu.com.cn/problem/P3793。
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e7 + 9;
int n, m, s, sgt[N << 1];
unsigned long long ans;
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);
}
} // namespace GenHelper
void srand(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;
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> m >> s, srand(s);
for (int i = 0; i < n; ++i) sgt[i + n] = read();
for (int i = n - 1; i; --i) sgt[i] = max(sgt[i << 1], sgt[i << 1 | 1]);
for (int l, r; m; --m) {
l = read() % n, r = read() % n;
if (l > r) swap(l, r);
int v = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) v = max(v, sgt[l++]);
if (r & 1) v = max(v, sgt[--r]);
}
ans += v;
}
return cout << ans << endl, 0;
}这就是我们的线段树啊，哎哎你们没有这样的线段树吗？
https://www.luogu.com.cn/team/55190。