loj#2212. 「SCOI2014」方伯伯的 OJ（splay）

loj#2212. 「SCOI2014」方伯伯的 OJ（splay）

题面在这里

做法

神奇的splay…..。>w<

放到第一名/最后一名显然可以转化成，删去后在头/尾部插入。

可以参考noip2017 D2T3的做法，用“离散排名”代替实际排名，也即用一个非连续的数列代替1~n。设置一个 mi/mx ，放到第一名就把它的排名设为 --mi ，放到最后一名就设为 ++mx 。

其次，用map保存编号为x的人的离散排名，用splay以排名为关键字维护这个有序数列。由于 n≤108 n ≤ 10 8 $nle 10^8$ ，不能够把所有数插入splay中，所以可以考虑插入一个区间，代表这个区间里的数都没有修改过。如果修改了区间中的某一个数，就把这个区间所在节点删去，插入两个新的区间。

注意离散排名和实际排名的区别。

此时的 siz[x] ，表示的是实际排名的子树 size ，也就是说一个节点的 size 为 r-l+1 。此时的 data[x] 表示的是排名为区间左端点的id，特别的，当 l=r l = r $l=r$ 时就直接表示排名为 l l <script type="math/tex" id="MathJax-Element-3">l</script> 的人的id。

于是求rk的时候找到这个编号的离散rk所对应的splay节点，就可以方便地算出真实rk了。具体见代码。

代码

=> 递归版写起来真的好简洁qwq
=> 注意数组大小！由于不仅会拆成新的两段插入，还会另外加入新的段（放到头/尾时），所以需要开4倍空间。

#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define ll long long
#define ld long double
#define inf 1000000000
using namespace std;
ll read(){char ch=getchar(); ll x=0; int op=1;for (; !isdigit(ch); ch=getchar()) if (ch=='-') op=-1;for (; isdigit(ch); ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';return x*op;
}
#define N 400005
int n,m,ans,mx,mi,rt,tot,L[N],R[N],data[N],ch[N][2],fa[N],siz[N]; map<int,int> Mp;
void up(int x){ siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+R[x]-L[x]+1; }
void rot(int x){int y=fa[x],z=fa[y],f=ch[y][1]==x;ch[y][f]=ch[x][f^1]; if (ch[x][f^1]) fa[ch[x][f^1]]=y;fa[x]=z; if (z) ch[z][ch[z][1]==y]=x;fa[y]=x; ch[x][f^1]=y; up(y); up(x);
}
void splay(int x,int tp){while (fa[x]!=tp){int y=fa[x],z=fa[y];if (z!=tp) rot((ch[y][0]==x)==(ch[z][0]==y)?y:x);rot(x);}if (!tp) rt=x;
}
void ins(int &x,int l,int r,int key,int pr){if (!x){x=++tot;ch[x][0]=ch[x][1]=0; fa[x]=pr;L[x]=l,R[x]=r,data[x]=key; siz[x]=r-l+1;//data存的是区间左端点的编号splay(x,0);return;}ins(ch[x][r>=L[x]],l,r,key,x);
}
int find(int x,int k){//查询离散排名为k的所在的节点if (L[x]<=k && k<=R[x]) return x;else return find(ch[x][k>R[x]],k);
}
int getkth(int x,int k){//查询实际排名为k的人的编号if (k>siz[ch[x][0]] && k<=siz[ch[x][0]]+R[x]-L[x]+1){if (L[x]==R[x]) return data[x];else return L[x]+k-siz[ch[x][0]]-1;}if (k<=siz[ch[x][0]]) return getkth(ch[x][0],k);else return getkth(ch[x][1],k-(siz[ch[x][0]]+R[x]-L[x]+1));
}
void del(int x,int k){//将x节点中删除k这个排名，并分成两个区间插入if (!ch[x][0]) rt=ch[x][1],fa[rt]=0; else{int y=ch[x][0];while (ch[y][1]) y=ch[y][1];//x前驱splay(y,x);//此时y没有右子树rt=y,fa[rt]=0;if (ch[x][1]) ch[y][1]=ch[x][1],fa[ch[x][1]]=y;up(rt);}if (L[x]<=k-1) ins(rt,L[x],k-1,L[x],0);if (k+1<=R[x]) ins(rt,k+1,R[x],k+1,0);
}
int main(){n=read(),m=read(); ans=0; mx=n,mi=0;//0表示没有修改过ins(rt,1,n,1,0);while (m--){int opt=read(),x=read()-ans,y,rk,tmp,now,nans;if (opt==4){ printf("%dn",ans=getkth(rt,x)); continue; }rk=Mp[x]; if (!rk) rk=x; //x的离散排名tmp=find(rt,rk); splay(tmp,0);printf("%dn",nans=siz[ch[tmp][0]]+rk-L[tmp]+1);del(tmp,rk);if (opt==1){y=read()-ans; ins(rt,rk,rk,y,0);Mp[y]=rk; Mp[x]=0;} else{Mp[x]=now=opt==2?--mi:++mx;ins(rt,now,now,x,0);}ans=nans;}return 0;
}