首先题意是告诉你要进行m次区间赋最值操作，要求你求出每一个值最后的大小，这题的难点在于查询m的次数是非常多的，高达1e8，所以你想用线段树边修改边查询是不可能的，（因为是随机出的数据，所以有一些剪枝被卡过去了，我女朋友就是这么过的，好气啊！！！）所以这个题用了我觉得很少见的一类数据结构ST表，ST的特征是可以用ologn的时间内建表，然后每次查询都是o（1）的，所以就是很适合这道题的特点了，因为这道题目也是有着多查询，和求最值的，所以我们使用了反着建立ST表的方法去实现这个东西，也是类似于dp的思想，上层是一个区间最大值，但是在dp的过程中，能把取最大值的路径合并一下，并使它的影响依然可以覆盖它的区间，这样逆序建立ST表可以处理区间最大值问题，并快速离线查询。
待更新：ST表的其他妙用（暂时还没想到这东西除了快速求最值外还有什么用，其实就是快速把可以混淆影响的区间结果以dp的方式传播到下一层吧）
#include<iostream> #include<cstring> #include <string> #include<algorithm> #include<map> #include<stack> #include<queue> #include <math.h> #include<vector> #define lson rt<<1 #define rson rt<<1|1 using namespace std; typedef long long ll; const int maxn=1e5+20; const int mod=1e9+7; typedef unsigned long long ull; typedef long long ll; const double pai=acos(-1),eps=1e-8; int k,len; unsigned int X,Y,Z; int st[maxn][20]; unsigned int rng61() { X=X^(X<<11); X=X^(X>>4); X=X^(X<<5); X=X^(X>>14); unsigned int W=X^(Y^Z); X=Y; Y=Z; Z=W; return Z; } int logg[maxn]; int main() { int T=1,num=0; for(int i=1;i<maxn;i++) { if(i<T*2) logg[i]=num; else{ T=T*2; num++; logg[i]=num; } } cin>>T; while(T--) { int n,m; scanf("%d%d%d%d%d",&n,&m,&X,&Y,&Z); // cin>>n>>m>>X>>Y>>Z; for(int i=30;i>=0;i--) { for(int j=1;j<=n;j++) st[j][i]=0; } for(int i=0;i<m;i++) { unsigned int a=rng61()%n+1,b=rng61()%n+1,c=rng61()%(1<<30); if(a>b) swap(a, b); int d=logg[(b-a+1)]; st[a][d]=max(st[a][d],(int)c); st[b-(1<<d)+1][d]=max(st[b-(1<<d)+1][d],(int)c); } for(int i=logg[n+1];i>0;i--) { for(int j=1;j<=n;j++) { int j2=j+(1<<(i-1)); if(j2<=n) st[j2][i-1]=max(st[j2][i-1],st[j][i]); st[j][i-1]=max(st[j][i],st[j][i-1]); } } ll ans=0; for(int i=1;i<=n;i++) ans^=(i*1LL)*st[i][0]; printf("%lld ",ans); } }