题意很直观，我就不说了。
解析:这是我以前没有接触过的线段树类型，有序表线段树，每个节点申请了两段空间，主要是为了保存左边儿子会有多少比v小的，右边儿子会有多少比v小
的，所以在建树过程中要归并排序。可能我讲起来比较难懂，详见代码，我给了注释。
代码
#include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<algorithm> using namespace std; typedef __int64 LL; #define e tree[id] #define lson tree[id*2] #define rson tree[id*2+1] const int mod=1e9+7; const int maxn=100005; const int C=~(1<<31),M=(1<<16)-1; int rnd(int last,int &a,int &b) { a=(36969+(last>>3))*(a&M)+(a>>16); b=(18000+(last>>3))*(b&M)+(b>>16); return (C&((a<<16)+b))%1000000000; } int n,m,A,B,a[maxn],b[maxn],c[maxn],xs[maxn]; bool cmp(const int& x,const int& y){ return b[x]<b[y]; } int data[maxn<<6],*p; int* New(int len){ p+=len; return p-len; } //静态的申请空间 void init() //离散化 { for(int i=0;i<n;i++) xs[i]=b[i]; sort(xs,xs+n); for(int i=0;i<n;i++) b[i]=upper_bound(xs,xs+n,b[i])-xs-1; for(int i=0;i<n;i++) a[i]=upper_bound(xs,xs+n,a[i])-xs-1; p=data; //在最开始的位置 } struct Tree { int le,ri,d,sum; int *lid,*rid; void Set(int v){ d=v; sum=v+1; } int GoLe(int v){ return v==-1?v:lid[v]; } //左边有多少<=v的 int GoRi(int v){ return v==-1?v:rid[v]; } //右边有多少<=v的 }tree[4*maxn]; void pushup(int id){ e.sum=lson.sum+rson.sum; } //取和 void pushdown(int id) { if(e.d!=-2) //延迟更新 { lson.Set(e.GoLe(e.d)); rson.Set(e.GoRi(e.d)); e.d=-2; } } void Build_tree(int id,int le,int ri) { e.le=le,e.ri=ri,e.d=-2; e.lid=New(ri-le+1); //左右都要申请空间 e.rid=New(ri-le+1); if(le==ri){ e.sum=(a[le]>=b[le]); return; } int mid=(le+ri)/2; Build_tree(id*2,le,mid); Build_tree(id*2+1,mid+1,ri); pushup(id); int ll=mid-le+1,rl=ri-mid; int *vl=b+le,*vr=b+mid+1; int i=0,j=0,cnt=0; while(i<ll&&j<rl) //归并排序 { if(vl[i]<vr[j]) //左边小于右边 { e.lid[cnt]=i; e.rid[cnt]=j-1; c[cnt++]=vl[i++]; } else { e.lid[cnt]=i-1; e.rid[cnt]=j; c[cnt++]=vr[j++]; } } while(i<ll) //左边没完的 { e.lid[cnt]=i; e.rid[cnt]=j-1; c[cnt++]=vl[i++]; } while(j<rl) //右边没完的 { e.lid[cnt]=i-1; e.rid[cnt]=j; c[cnt++]=vr[j++]; } int k=0; for(int i=le;i<=ri;i++) b[i]=c[k++]; } void Update(int id,int x,int y,int v) //更新 { int le=e.le,ri=e.ri; if(x<=le&&ri<=y){ e.Set(v); return; } //在区间内 pushdown(id); int mid=(le+ri)/2; if(x<=mid) Update(id*2,x,y,e.GoLe(v)); //左边GoLe代表左边有多少<=v的 if(y>mid) Update(id*2+1,x,y,e.GoRi(v));//右边同理 pushup(id); } int Query(int id,int x,int y) //查询 { int le=e.le,ri=e.ri; if(x<=le&&ri<=y) return e.sum; //在区间内直接返回值 pushdown(id); //延迟更新 int mid=(le+ri)/2; int ret=0; if(x<=mid) ret+=Query(id*2,x,y); //加上左边 if(y>mid) ret+=Query(id*2+1,x,y); //加上右边 return ret; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d%d%d",&n,&m,&A,&B); for(int i=0;i<n;i++) scanf("%d",&a[i]); //输入 for(int i=0;i<n;i++) scanf("%d",&b[i]); init(); Build_tree(1,0,n-1); //建树 int last=0,ret=0; for(int i=1;i<=m;i++) { int l=rnd(last,A,B)%n; int r=rnd(last,A,B)%n; int x=rnd(last,A,B)+1; if(l>r) swap(l,r); if((l+r+x)%2) //为奇数是插入 { x=upper_bound(xs,xs+n,x)-xs-1; Update(1,l,r,x); } else //否则查询 { last=Query(1,l,r); ret=(ret+(LL)i*last%mod)%mod; } } printf("%d ",ret); } return 0; }