第一种用线段树，用两颗数维护区间最大值和区间的最小值，然后更新的时候如果我目前区间内的最大值比我得到的v小，那么我就把这个区间修改成v，如果我的最小值比v大，那么v就是没有用的，直接跳过，然后这样每次更新[l, r]内的最大最小值，查询的时候返回每个位置的最大值，就可以求出答案
线段树：
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x & (-x)) typedef unsigned long long int ull;
typedef long long int ll;
typedef unsigned int ui;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 1e5;
const int maxm = 2e5+;
const int mod = <<;
const double eps = 1e-;
using namespace std; int n, m;
int T, tol;
ui X, Y, Z;
int mx[maxn << ];
int mn[maxn << ];
int lazy[maxn << ]; ui RNG61() {
X = X ^ (X<<);
X = X ^ (X>>);
X = X ^ (X<<);
X = X ^ (X>>);
ll W = X ^ (Y ^ Z);
X = Y;
Y = Z;
Z = W;
return Z;
} void init() {
memset(mx, , sizeof mx);
memset(mn, , sizeof mn);
memset(lazy, , sizeof lazy);
} void pushup(int root) {
mx[root] = max(mx[root << ], mx[root << | ]);
mn[root] = min(mn[root << ], mn[root << | ]);
} void pushdown(int root) {
if(lazy[root]) {
mx[root << ] = mx[root << | ] = lazy[root];
mn[root << ] = mn[root << | ] = lazy[root];
lazy[root << ] = lazy[root << | ] = lazy[root];
lazy[root] = ;
}
} void update(int left, int right, int prel, int prer, int val, int root) {
if(prel <= left && right <= prer) {
if(mx[root] < val) {
mx[root] = mn[root] = val;
lazy[root] = val;
return ;
}
if(mn[root] > val) return ;
}
if(mn[root] > val) return ;
pushdown(root);
int mid = (left + right) >> ;
if(prel <= mid) update(left, mid, prel, prer, val, root << );
if(prer > mid) update(mid+, right, prel, prer, val, root << | );
pushup(root);
} int query(int left, int right, int pos, int root) {
if(left == right) {
return mx[root];
}
pushdown(root);
int mid = (left + right) >> ;
if(pos <= mid) return query(left, mid, pos, root << );
else return query(mid+, right, pos, root << | );
} int main() {
scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d%d", &n, &m, &X, &Y, &Z);
init();
for(int i=; i<=m; i++) {
ui f1 = RNG61();
ui f2 = RNG61();
ui f3 = RNG61();
int l = min(f1%n+, f2%n+);
int r = max(f1%n+, f2%n+);
int v = f3 % mod;
update(, n, l, r, v, );
}
ll ans = ;
for(int i=; i<=n; i++) {
ans ^= (1ll * i * query(, n, i, ));
}
printf("%I64d\n", ans);
}
return ;
}
原本的RMQ是得到每个位置的点值，然后一步一步更新成区间的最值，用
st[i][j] = max(st[i][j-1]，st[i+(1<<(j-1))][j-1])
然后这里是先得到区间最值，然后往回更新到每个位置的点的最值，所以就是两个
st[i][j-1] = max(st[i][j-1], st[i][j])
st[i+(1<<(j-1))][j-1] = max(st[i+(1<<(j-1))][j-1], st[i][j])
倒着更新
然后题目里面数据很大，所以同样的log(r-l+1)/log(2.0)可能计算很多遍，可以把log(i)/log(2.0)打表出来，可以快一半的时间
ST表：
#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lowbit(x) (x & (-x)) typedef unsigned long long int ull;
typedef long long int ll;
typedef unsigned int ui;
const double pi = 4.0*atan(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 1e5;
const int maxm = 2e5+;
const int mod = <<;
const double eps = 1e-;
using namespace std; int n, m;
int T, tol;
ui X, Y, Z; int st[maxm][];
int lg[maxn]; ui RNG61() {
X = X ^ (X<<);
X = X ^ (X>>);
X = X ^ (X<<);
X = X ^ (X>>);
ll W = X ^ (Y ^ Z);
X = Y;
Y = Z;
Z = W;
return Z;
} void init() {
memset(st, , sizeof st);
} void handle() {
lg[] = -;
for(int i=; i<maxn; i++) lg[i] = log(i) / log(2.0);
} int main() {
handle();
scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d%d", &n, &m, &X, &Y, &Z);
init();
for(int i=; i<=m; i++) {
ui f1 = RNG61();
ui f2 = RNG61();
ui f3 = RNG61();
int l = min(f1%n+, f2%n+);
int r = max(f1%n+, f2%n+);
int v = f3 % mod;
int k = lg[r-l+];
st[l][k] = max(st[l][k], v);
st[r-(<<k)+][k] = max(st[r-(<<k)+][k], v);
}
int len = log(n) / log(2.0);
for(int j=len; j>=; j--) {
for(int i=; i<=n; i++) {
st[i][j-] = max(st[i][j-], st[i][j]);
st[i+(<<(j-))][j-] = max(st[i+(<<(j-))][j-], st[i][j]);
}
}
ll ans = ;
for(int i=; i<=n; i++) ans = ans ^ (1ll * i * st[i][]);
printf("%I64d\n", ans);
}
return ;
}