【JZOJ6030】白白的

Description

Solution

单点修改操作：树状数组套线段树。
分裂操作：类似启发式那样求跨越分裂点的逆序对数。
还有就是注意求的是异或和。

Code

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
#define fo(i,j,k) for(int i=j;i<=k;++i)
#define fd(i,j,k) for(int i=j;i>=k;--i)
using namespace std;
typedef multiset<int> :: iterator it;
typedef long long ll;
const int N=15e4+10,inf=1e9;
int n;
struct P{int l,r,x;P(int _l=0,int _r=0,int _x=0) {l=_l,r=_r,x=_x;}
}tr[N*540];
int read(){char ch=' ';int t=0;for(;ch<'0' || ch>'9';ch=getchar());for(;ch>='0' && ch<='9';ch=getchar()) t=(t<<1)+(t<<3)+ch-48;return t;
}
ll readll(){char ch=' ';ll t=0;for(;ch<'0' || ch>'9';ch=getchar());for(;ch>='0' && ch<='9';ch=getchar()) t=(t<<1)+(t<<3)+ch-48;return t;
}
multiset<int> s;
P b[N];
ll c[N];
int a[N],d[N],cnt=1;
int rt[N+N],tot=0;
/*int st[N*110],top=0;
int newnode(){return !top?++tot:st[top--];
}*/
void seg_add(int x,int t,int &v,int l=0,int r=inf){if(!v) /*v=newnode()*/v=++tot;tr[v].x+=t;if(l<r){int mid=(l+r)>>1;x<=mid?seg_add(x,t,tr[v].l,l,mid):seg_add(x,t,tr[v].r,mid+1,r);}//if(!tr[v].x) st[++top]=v,v=0;
}
int seg_sum(int x,int v,int l=0,int r=inf){if(!v || l>x) return 0;if(r<=x) return tr[v].x;int mid=(l+r)>>1;return seg_sum(x,tr[v].l,l,mid)+seg_sum(x,tr[v].r,mid+1,r);
}
void add(int x,int p,int t){for(;x<=n;x+=x&-x) seg_add(p,t,rt[x]);
}
int sum(int x,int t){if(t<0) return 0;int tmp=0;for(;x;x-=x&-x) tmp+=seg_sum(t,rt[x]);return tmp;
}
int calc(int l,int r,int t){return l>r?0:sum(r,t)-sum(l-1,t);
}
int main()
{freopen("baibaide4-5.in","r",stdin);freopen("baibaide.out","w",stdout);n=read();int q=read(),type=1;fo(i,1,n) a[i]=read(),seg_add(a[i],1,rt[cnt+n]);s.insert(1);ll ans=0;fo(i,1,n)ans+=i-1-calc(1,i-1,a[i]),add(i,a[i],1);b[1]=P(1,n,cnt),c[cnt]=ans;fo(zz,1,q){int op=read(),x=readll()^(zz>type?ans:0);it p=s.upper_bound(x);--p;int l=*p,r=b[l].r,z=b[l].x;if(!op){int y=readll()^(zz>type?ans:0),t=0;t-=x-l-calc(l,x-1,a[x]),t-=calc(x+1,r,a[x]-1);add(x,a[x],-1),seg_add(a[x],-1,rt[z+n]);a[x]=y,add(x,a[x],1),seg_add(a[x],1,rt[z+n]);t+=x-l-calc(l,x-1,a[x]),t+=calc(x+1,r,a[x]-1);ans^=c[z],c[z]+=t,ans^=c[z];}else{ll t=0;ans^=c[z];if(x-l<r-x){if(l<x) ++cnt;fo(i,l,x) seg_add(a[i],-1,rt[z+n]);fo(i,l,x-1){c[cnt]+=i-l-seg_sum(a[i],rt[cnt+n]);t+=seg_sum(a[i]-1,rt[z+n]),seg_add(a[i],1,rt[cnt+n]);}t+=seg_sum(a[x]-1,rt[z+n]);if(l<x){t+=x-l-seg_sum(a[x],rt[cnt+n]);b[l]=P(l,x-1,cnt);}else b[l]=P(0,0,0),s.erase(s.find(l));s.insert(x+1),b[x+1]=P(x+1,r,z);int w=l<x?c[cnt]:0;c[z]-=t+w,ans^=c[z]^w;}else{if(x<r) ++cnt;fo(i,x,r) seg_add(a[i],-1,rt[z+n]);fo(i,x+1,r){c[cnt]+=i-x-1-seg_sum(a[i],rt[cnt+n]);t+=x-l-seg_sum(a[i],rt[z+n]),seg_add(a[i],1,rt[cnt+n]);}t+=x-l-seg_sum(a[x],rt[z+n]);if(x<r){t+=seg_sum(a[x]-1,rt[cnt+n]);b[l]=P(l,x-1,z);s.insert(x+1),b[x+1]=P(x+1,r,cnt);}else if(l<x) b[l]=P(l,x-1,z);else b[l]=P(0,0,0),s.erase(s.find(l));int w=x<r?c[cnt]:0;c[z]-=t+w,ans^=c[z]^w;}}printf("%lld\n",ans);}
}