首先思考一个朴素的做法

将b[]维护成一个线段树套有序表，每次修改a[]用线段树+lazy tag

并在线段树的子区间上在有序表中二分更新这段区间中a[i]>=b[i]的值，复杂度O(nlog^2)

有没有更优的做法？

考虑在一次修改操作中，查询的数是相同的，并且b[]这个有序表始终不变

因此在生成b[]的线段树套有序表过程中（其实就是归并排序的记录）

我们维护每个数在左右子区间中名次。

这样修改的时候我们只要对b[]排好序的整体做一次二分，找到b[m]<=x<b[m+1]

把修改成x当作修改成b[m]，这样我们就能O(1)地更新每个子区间的计数，问题得解

1 #include
      
         2 #define mp make_pair  3 using namespace std;  4 const int mo=1000000007;  5 vector< pair
       
         > tr[100010*4];  6 int laz[100010*4],s[100010*4],a[100010],b[100010],c[100010];  7 int A,B,n,m,t;  8 int C = ~(1<<31), M = (1<<16)-1;  9 int rnd(int last,int &a,int &b) 10 { 11     a = (36969 + (last >> 3)) * (a & M) + (a >> 16); 12     b = (18000 + (last >> 3)) * (b & M) + (b >> 16); 13     return (C & ((a << 16) + b)) % 1000000000; 14 } 15  16 void build(int i,int l,int r) 17 { 18     laz[i]=-2; 19     tr[i].clear(); 20     if (l==r) 21     { 22         s[i]=(a[l]>=b[l]); 23     } 24     else { 25         int m=(l+r)>>1; 26         build(i*2,l,m); 27         build(i*2+1,m+1,r); 28         s[i]=s[i*2]+s[i*2+1]; 29         int x=l,y=m+1,h=l; 30         while (x<=m&&y<=r) 31         { 32             if (b[x]
        
         =r) 69     { 70         laz[i]=w; 71         s[i]=w+1; 72     } 73     else { 74         int m=(l+r)>>1; 75         if (laz[i]>-2) push(i); 76         if (x<=m) add(i*2,l,m,x,y,w==-1?w:tr[i][w].first); 77         if (y>m) add(i*2+1,m+1,r,x,y,w==-1?w:tr[i][w].second); 78         s[i]=s[i*2]+s[i*2+1]; 79     } 80 } 81  82 int ask(int i,int l,int r,int x,int y) 83 { 84     if (x<=l&&y>=r) return s[i]; 85     else { 86         int m=(l+r)>>1,ans=0; 87         if (laz[i]>-2) push(i); 88         if (x<=m) ans+=ask(i*2,l,m,x,y); 89         if (y>m) ans+=ask(i*2+1,m+1,r,x,y); 90         return ans; 91     } 92 } 93  94 int main() 95 { 96     int cas; 97     scanf("%d",&cas); 98     while (cas--) 99     {100         scanf("%d%d%d%d",&n,&m,&A,&B);101         for (int i=1; i<=n; i++) scanf("%d",&a[i]);102         for (int i=1; i<=n; i++) scanf("%d",&b[i]);103         b[n+1]=2147483647;104         build(1,1,n);105         int ans=0;106         int last=0;107         for (int i=1; i<=m; i++)108         {109             int l=rnd(last,A,B)%n+1,r=rnd(last,A,B)%n+1,x=rnd(last,A,B)+1;110             if (l>r) swap(l,r);111             if ((l+r+x)%2==0)112             {113                 last=ask(1,1,n,l,r);114                 ans=(ans+1ll*i*last%mo)%mo;115             }116             else {117                 int w=upper_bound(b+1,b+1+n,x)-b-2;118                 add(1,1,n,l,r,w);119             }120         }121         printf("%d\n",ans);122     }123 }