白白的（baibaide）

有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，一开始每个位置都是白色。如果一个区间中每个位置都是白色，则称这是一个白白的区间。如果一个白白的区间向左或向右延长后都不是白白的区间了，则称这是一个极长的白白的区间。有 $q$ 次操作，每次操作会修改某个位置的值，或者把某个位置变成黑色。每次操作后，求所有极长的白白的区间中含有的逆序对数的异或和。强制在线。

$n ≤ 150000，q ≤ 20000，0 ≤ a_i ≤ 10^9，1 ≤ x ≤ n，0 ≤ y ≤ 10^9$

$Subtask1(10pts) : n ≤ 10^3, q ≤ 10^3$

$Subtask2(20pts) : 只有 0 操作$

$Subtask3(30pts) : 只有 1 操作$

$Subtask4(40pts) : 没有特殊限制$

---

Solution

毒题

有种高级的东西叫做启发式分裂，可以应用于只分裂不合并的题目。

每次扫描较小的那一段，复杂度似乎是nlogn的。

那我们考虑每次枚举小的那一段区间的每个数x，然后在大的区间中查找比x大（小）的数的个数，也就是x对于大区间的逆序对贡献。

大区间的答案等于原来区间的答案减去每次查出的答案，小的重新算。

统计小于？主席树就行。修改？树套树。

然而这题没完...

我们算下复杂度:分裂$nlogn$ ，树套树 $nlog^2n$ ，修改 $qlog^2n$

总复杂度 $ nlog^3n + qlog^2n $

n=150000 炸了

我们考虑优化前面的那个^3

按权值为比较大小的关键字建splay

一棵splay维护一段区间，分裂时查询某一段比x大的有几个。

分裂完小的区间暴力重建splay，总共可以有多棵splay

这样前面就是$nlog^2n$了

树套树似乎不用了？然而splay在单点修改时不能维护答案，于是还要。

总复杂度 $ nlog^2n + qlog^2n $

颠覆我对数据结构的认知

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #define ll long long 9 #define maxn 150005 10 #define Max 1000000000 11 using namespace std; 12 int n,q,a[maxn],rt[maxn],tot,cnt,root[maxn]; 13 ll Ans,ans[maxn]; 14 struct no{ 15 int ls,rs,v; 16 }tr[maxn*400]; 17 set
             
              dd; 18 void wh(int k){ 19 tr[k].v=tr[tr[k].ls].v+tr[tr[k].rs].v; 20 } 21 void add(int &k,int l,int r,int pl,int v){ 22 if(!k)k=++cnt; 23 if(l==r){ 24 tr[k].v+=v; 25 return; 26 } 27 int mid=l+r>>1; 28 if(pl<=mid)add(tr[k].ls,l,mid,pl,v); 29 else add(tr[k].rs,mid+1,r,pl,v); 30 wh(k); 31 } 32 ll t_ask(int k,int l,int r,int v,int fl){ 33 if(!k)return 0; 34 ll sl=0,sr=0; 35 if(l==r){ 36 return tr[k].v; 37 } 38 int mid=l+r>>1; 39 if(fl==1){ //>v 40 if(v<=mid)return tr[tr[k].rs].v+t_ask(tr[k].ls,l,mid,v,fl); 41 else return t_ask(tr[k].rs,mid+1,r,v,fl); 42 } 43 else{ 44 if(v<=mid)return t_ask(tr[k].ls,l,mid,v,fl); 45 else return tr[tr[k].ls].v+t_ask(tr[k].rs,mid+1,r,v,fl); 46 } 47 } 48 ll ask(int l,int r,int v,int fl){ 49 if(l>r)return 0; 50 ll sl=0,sr=0; 51 if(fl)v++;else v--; 52 if(l-1>0)for(int i=l-1;i;i-=i&-i)sl+=t_ask(root[i],0,Max,v,fl); 53 for(int i=r;i;i-=i&-i)sr+=t_ask(root[i],0,Max,v,fl); 54 return sr-sl; 55 } 56 ll query(int l,int r,int x){ 57 ll n1=0,n2=0; 58 n1=ask(l,x-1,a[x],1);n2=ask(x+1,r,a[x],0); 59 return n1+n2; 60 } 61 struct Splay{ 62 int ch[2],f,v,num,sz; 63 }t[maxn*50]; 64 void upd(int x){ 65 int ls=t[x].ch[0],rs=t[x].ch[1]; 66 t[x].sz=t[ls].sz+t[rs].sz+t[x].num; 67 } 68 int get(int x){ return t[t[x].f].ch[1]==x;} 69 void rotate(int x){ 70 int y=t[x].f,z=t[y].f; 71 int wx=get(x),wy=get(y); 72 t[z].ch[wy]=x;t[x].f=z; 73 t[y].ch[wx]=t[x].ch[wx^1];t[t[x].ch[wx^1]].f=y; 74 t[x].ch[wx^1]=y;t[y].f=x; 75 upd(y);upd(x); 76 } 77 void splay(int x,int g){ 78 while(t[x].f!=g){ 79 int y=t[x].f,z=t[y].f; 80 if(z!=g)rotate(get(x)==get(y)?y:x); 81 rotate(x); 82 } 83 } 84 void modify(int &R,int k,int x,int Num){ 85 int fa=0; 86 while(k&&t[k].v!=x){ 87 fa=k,k=t[k].ch[x>t[k].v]; 88 } 89 if(k)t[k].num+=Num; 90 else { 91 k=++tot; 92 if(fa)t[fa].ch[x>t[fa].v]=k; 93 t[k].v=x;t[k].num=t[k].sz=1;t[k].f=fa; 94 } 95 splay(k,0);R=k; 96 } 97 ll ask_min(int k,int v){ 98 ll sum=0; 99 while(k){100 if(t[k].v
              110 ll sum=0;111 while(k){112 if(t[k].v
              
               >n>>q;dd.insert(1);dd.insert(n+1);124 for(int i=1;i<=n;i++){125 scanf("%d",&a[i]);126 modify(rt[1],rt[1],a[i],1);127 }128 for(int i=1;i<=n;i++)129 for(int j=i;j<=n;j+=j&-j){130 add(root[j],0,Max,a[i],1);131 }132 for(int i=1;i<=n;i++)ans[1]+=query(1,n,i);133 ans[1]/=2;Ans=ans[1];ll la=0;134 for(int i=1,op;i<=q;i++){135 scanf("%d",&op);136 ll x,y;137 if(op==0){138 scanf("%lld%lld",&x,&y);x^=la;y^=la;139 set
               
                ::iterator it;140 it=dd.upper_bound(x);141 int r=*it-1;it--;int l=*it;142 Ans^=ans[l];143 ll num=query(l,r,x);144 modify(rt[l],rt[l],a[x],-1);145 ans[l]-=num;146 for(int j=x;j<=n;j+=j&-j)add(root[j],0,Max,a[x],-1);147 a[x]=y;148 modify(rt[l],rt[l],a[x],1);149 for(int j=x;j<=n;j+=j&-j)add(root[j],0,Max,a[x],1);150 num=query(l,r,x);151 ans[l]+=num;Ans^=ans[l];152 printf("%lld\n",Ans);la=Ans;153 }154 else {155 scanf("%lld",&x);x^=la;156 set
                
                 ::iterator it;157 it=dd.upper_bound(x);158 int r=*it-1;it--;int l=*it;159 Ans^=ans[l];ll co=0;160 if(x==l){161 co=ask_min(rt[l],a[l]);162 modify(rt[l],rt[l],a[l],-1);163 ans[l+1]=ans[l]-co;ans[l]=0;164 rt[l+1]=rt[l];rt[l]=0;165 Ans^=ans[l+1];166 dd.insert(l+1);167 }168 else if(x==r){169 co=ask_max(rt[l],a[r]);170 modify(rt[l],rt[l],a[r],-1);171 ans[l]-=co;Ans^=ans[l];172 dd.insert(r);173 }174 else {175 if(x-l
                 
                  =x;i--){190 co+=ask_max(rt[l],a[i]);191 modify(rt[l],rt[l],a[i],-1);192 }193 ans[l]-=co;194 for(int i=x+1;i<=r;i++){195 modify(rt[x+1],rt[x+1],a[i],1);196 ans[x+1]+=ask_max(rt[x+1],a[i]);197 }198 Ans=(Ans^ans[l]^ans[x+1]);199 }200 dd.insert(x);dd.insert(x+1);201 }202 printf("%lld\n",Ans);la=Ans;203 }204 }205 return 0;206 }