第一种用线段树，用两颗数维护区间最大值和区间的最小值，然后更新的时候如果我目前区间内的最大值比我得到的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+10; const int mod = 1<<30; const double eps = 1e-8; using namespace std; int n, m; int T, tol; ui X, Y, Z; int mx[maxn << 2]; int mn[maxn << 2]; int lazy[maxn << 2]; ui RNG61() { X = X ^ (X<<11); X = X ^ (X>>4); X = X ^ (X<<5); X = X ^ (X>>14); ll W = X ^ (Y ^ Z); X = Y; Y = Z; Z = W; return Z; } void init() { memset(mx, 0, sizeof mx); memset(mn, 0, sizeof mn); memset(lazy, 0, sizeof lazy); } void pushup(int root) { mx[root] = max(mx[root << 1], mx[root << 1 | 1]); mn[root] = min(mn[root << 1], mn[root << 1 | 1]); } void pushdown(int root) { if(lazy[root]) { mx[root << 1] = mx[root << 1 | 1] = lazy[root]; mn[root << 1] = mn[root << 1 | 1] = lazy[root]; lazy[root << 1] = lazy[root << 1 | 1] = lazy[root]; lazy[root] = 0; } } 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) >> 1; if(prel <= mid) update(left, mid, prel, prer, val, root << 1); if(prer > mid) update(mid+1, right, prel, prer, val, root << 1 | 1); pushup(root); } int query(int left, int right, int pos, int root) { if(left == right) { return mx[root]; } pushdown(root); int mid = (left + right) >> 1; if(pos <= mid) return query(left, mid, pos, root << 1); else return query(mid+1, right, pos, root << 1 | 1); } int main() { scanf("%d", &T); while(T--) { scanf("%d%d%d%d%d", &n, &m, &X, &Y, &Z); init(); for(int i=1; i<=m; i++) { ui f1 = RNG61(); ui f2 = RNG61(); ui f3 = RNG61(); int l = min(f1%n+1, f2%n+1); int r = max(f1%n+1, f2%n+1); int v = f3 % mod; update(1, n, l, r, v, 1); } ll ans = 0; for(int i=1; i<=n; i++) { ans ^= (1ll * i * query(1, n, i, 1)); } printf("%I64d ", ans); } return 0; }
原本的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+10; const int mod = 1<<30; const double eps = 1e-8; using namespace std; int n, m; int T, tol; ui X, Y, Z; int st[maxm][20]; int lg[maxn]; ui RNG61() { X = X ^ (X<<11); X = X ^ (X>>4); X = X ^ (X<<5); X = X ^ (X>>14); ll W = X ^ (Y ^ Z); X = Y; Y = Z; Z = W; return Z; } void init() { memset(st, 0, sizeof st); } void handle() { lg[0] = -1; for(int i=1; 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=1; i<=m; i++) { ui f1 = RNG61(); ui f2 = RNG61(); ui f3 = RNG61(); int l = min(f1%n+1, f2%n+1); int r = max(f1%n+1, f2%n+1); int v = f3 % mod; int k = lg[r-l+1]; st[l][k] = max(st[l][k], v); st[r-(1<<k)+1][k] = max(st[r-(1<<k)+1][k], v); } int len = log(n) / log(2.0); for(int j=len; j>=1; j--) { for(int i=1; i<=n; i++) { 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]); } } ll ans = 0; for(int i=1; i<=n; i++) ans = ans ^ (1ll * i * st[i][0]); printf("%I64d ", ans); } return 0; }