题目
【题目描述】
有一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，一开始每个位置都是白色。如果一个区间中每个位置都是白色，则称这是一个白白的区间。如果一个白白的区间向左或向右延长后都不是白白的区间了，则称这是一个极长的白白的区间。有 $q$ 次操作，每次操作会修改某个位置的值，或者把某个位置变成黑色。每次操作后，求所有极长的白白的区间中含有的逆序对数的异或和。强制在线。
【输入格式】
第一行两个正整数 $n, q$。
第二行 $n$ 个正整数 $a_1, a_2, \dots, a_n$。
接下来 $q$ 行，每行表示一次操作，每行的第一个数表示操作的种类：
$• ~ 0 ~ x ~ y$ 表示把 $a_x$ 改为 $y$
$• ~ 1 ~ x$ 表示把第 $x$ 个位置变成黑色
保证每次操作时的第 $x$ 个位置是白色的。
$x$ 和 $y$ 需要异或上一次输出的答案（若是第一次操作则无需异或）。
【输出格式】
$q$ 行，每行一个整数，表示每次询问的答案。
【样例输入】
4 3
6 0 10 1
1 2
1 0
1 2
【样例输出】
1
1
0
【数据范围与提示】
$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) : 没有特殊限制$
题解
这是一道极其毒瘤的数据结构题
求一段区间的逆序对个数，自然是用树状数组，但要支持修改和分裂，那么就套主席树，启发式分裂
效率：$ O(nlog^3n) $，很遗憾，这样子常数太大，而且这道题卡常
出题人发现，其实修改和分裂是可以分开做的
修改时直接在树套树上查询和修改即可，至于分裂时，其实要找的只有在它前面比它大的个数，可以每一个区间开一个 splay 查询，类似于启发式，暴力删，然后重构一个新的 splay
其实就是利用分裂时的特殊性质用 splay 优化树套树的分裂过程
大概要分讨一下前面的区间和后面的区间的大小
时间效率：$ O(nlog^2n)$
写到醉生梦死
代码
#include<bits/stdc++.h>
#define LL long long
#define _(d) while(d(isdigit(ch=getchar())))
using namespace std;
int R(){
int x;bool f=;char ch;_(!)if(ch=='-')f=;x=ch^;
_()x=(x<<)+(x<<)+(ch^);return f?x:-x;}
const int N=2e5+,INF=1e9+;
int n,q,a[N],Rt[N],li[N];
LL ans,las,sum[N];
set<int>s;
set<int>::iterator it;
class Splay{
private:
#define Ls(x) ch[x][0]
#define Rs(x) ch[x][1]
public:
int val[N*],fa[N*],siz[N*],num[N*],ch[N*][],cnt;
void pushup(int x){siz[x]=siz[Ls(x)]+siz[Rs(x)]+num[x];}
int init(){
cnt+=;
fa[cnt]=cnt-,Rs(cnt-)=cnt;
val[cnt]=INF,val[cnt-]=;
siz[cnt]=siz[cnt-]=num[cnt]=num[cnt-]=;
return cnt-;
}
int find_xi(int rt,int x){
if(!rt)return ;
if(val[rt]==x)return rt;
if(val[rt]<x){
int f=find_xi(Rs(rt),x);
return f?f:rt;
}
return find_xi(Ls(rt),x);
}
int find_da(int rt,int x){
if(!rt)return ;
if(val[rt]==x)return rt;
if(val[rt]>x){
int f=find_da(Ls(rt),x);
return f?f:rt;
}
return find_da(Rs(rt),x);
}
void rotate(int &k,int x){
int y=fa[x],z=fa[y],fl=(Rs(y)==x),w=ch[x][!fl];
if(y==k)k=x;
else ch[z][Rs(z)==y]=x;
ch[x][!fl]=y,ch[y][fl]=w;
if(w)fa[w]=y;fa[y]=x,fa[x]=z;
pushup(y),pushup(x);
return;
}
void splay(int &k,int x){
while(x!=k){
int y=fa[x];
if(y!=k)
rotate(k,(Ls(fa[x])==x)^(Ls(fa[y])==y)?x:y);
rotate(k,x);
}
}
void insert(int id,int x,int v){
int now=find_xi(Rt[id],x);
if(val[now]==x){
splay(Rt[id],now),num[now]+=v,pushup(now);
return;
}
int nex=find_da(Rt[id],x);
splay(Rt[id],now),splay(Rs(now),nex);
cnt++,val[cnt]=x,num[cnt]=siz[cnt]=;
fa[cnt]=nex,ch[nex][]=cnt;
pushup(nex),pushup(now);
return;
}
#undef Ls
#undef Rs
}T;
int cnt,rot[N];
struct seg{int ls,rs,v;}tr[N*];
#define Ls tr[rt].ls
#define Rs tr[rt].rs
LL query(int rt,int l,int r,int ql,int qr){
if(!rt)return ;
if(ql<=l&&qr>=r)return tr[rt].v;
int mid=(l+r)>>;LL res=;
if(ql<=mid)res=query(Ls,l,mid,ql,qr);
if(qr>mid)res+=query(Rs,mid+,r,ql,qr);
return res;
}
void insert(int &rt,int l,int r,int k,int v){
if(!rt)rt=++cnt;tr[rt].v+=v;
if(l==r)return;
int mid=(l+r)>>;
if(k<=mid)insert(Ls,l,mid,k,v);
else insert(Rs,mid+,r,k,v);
return;
}
LL ask(int l,int r,int ql,int qr){
if(ql>qr||l>r)return ;
LL ans=;
for(;r;r-=r&-r)ans+=query(rot[r],,INF,ql,qr);
for(;l;l-=l&-l)ans-=query(rot[l],,INF,ql,qr);
return ans;
}
void add(int k,int x,int f){for(;k<=n;k+=k&-k)insert(rot[k],,INF,x,f);}
int main(){
n=R(),q=R(),Rt[n]=T.init();
for(int i=;i<=n;i++)
a[i]=R()+,T.insert(n,a[i],);
s.insert(n),li[n]=;
for(int i=;i<=n;i++){
ans+=ask(,i-,a[i]+,INF);
add(i,a[i],);}
sum[n]=ans;
while(q--){
int op=R(),x=(LL)R()^las,y,l,r;
it=s.lower_bound(x);
r=(*it),l=li[r],ans^=sum[r];
if(!op){
y=(LL)(R()^las)+;
sum[r]-=ask(l-,x-,a[x]+,INF)+ask(x,r,,a[x]-);
T.insert(r,a[x],-),T.insert(r,y,);
add(x,a[x],-),add(x,a[x]=y,);
sum[r]+=ask(l-,x-,a[x]+,INF)+ask(x,r,,a[x]-);
ans^=sum[r];
}
if(op){
li[r]=x+,T.insert(r,a[x],-);
s.insert(x-),li[x-]=l,sum[x-]=;
LL num=(LL)ask(l-,x-,a[x]+,INF)+ask(x,r,,a[x]-);
if(x-l<r-x){
if(l!=x)Rt[x-]=T.init();
for(int i=l;i<x;i++){
T.insert(r,a[i],-);
int k=T.find_da(Rt[r],a[i]);
T.splay(Rt[r],k),num+=T.siz[T.ch[k][]];
T.insert(x-,a[i],);
k=T.find_da(Rt[x-],a[i]);
T.splay(Rt[x-],k);
sum[x-]+=T.siz[T.ch[k][]];
}
sum[r]-=num,ans^=sum[x-]^sum[r];
}
else{
swap(sum[r],sum[x-]),swap(Rt[r],Rt[x-]);
Rt[r]=T.init(),sum[r]=;
for(int i=r;i>x;i--){
T.insert(x-,a[i],-);
int k=T.find_da(Rt[x-],a[i]);
T.splay(Rt[x-],k),num+=T.siz[T.ch[k][]];
T.insert(r,a[i],);
k=T.find_da(Rt[r],a[i]);
T.splay(Rt[r],k);
sum[r]+=T.siz[T.ch[k][]];
}
sum[x-]-=num,ans^=sum[x-]^sum[r];
}
}
printf("%lld\n",las=ans);
}
return ;
}