洛谷 P3285 / loj 2212 [SCOI2014] 方伯伯的 OJ 题解【平衡树】【线段树】
点击量：203
平衡树分裂钛好玩辣！
题目描述
方伯伯正在做他的 OJ。现在他在处理 OJ 上的用户排名问题。
OJ 上注册了 $ n$ 个用户，编号为 $ 1\sim n$，一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作，修改用户的排名和编号：
- 操作格式为
1 x y，意味着将编号为 $ x$ 的用户编号改为 $ y$，而排名不变，执行完该操作后需要输出该用户在排名中的位置，数据保证 $ x$ 必然出现在排名中，同时 $ y$ 是一个当前不在排名中的编号。- 操作格式为
2 x，意味着将编号为 $ x$ 的用户的排名提升到第一位，执行完该操作后需要输出执行该操作前编号为 $ x$ 用户的排名。- 操作格式为
3 x，意味着将编号为 $ x$ 的用户的排名降到最后一位，执行完该操作后需要输出执行该操作前编号为 $ x$ 用户的排名。- 操作格式为
4 k，意味着查询当前排名为 $ k$ 的用户编号，执行完该操作后需要输出当前操作用户的编号。 但同时为了防止别人监听自己的工作，方伯伯对他的操作进行了加密，即将四种操作的格式分别改为了：1 x+a y+a 2 x+a 3 x+a 4 k+a其中 $ a$ 为上一次操作得到的输出，一开始 $ a=0$。
例如： 上一次操作得到的输出是
5，
这一次操作的输入为：1 13 15，
因为这个输入是经过加密后的，所以你应该处理的操作是1 8 10。现在你截获了方伯伯的所有操作，希望你能给出结果。
输入输出格式
输入格式：
输入的第一行包含两个用空格分隔的整数 $ n$ 和 $ m$，表示初始用户数和操作数。
此后有 $ m$ 行，每行是一个询问，询问格式如上所示。
输出格式：
输出包含 $ m$ 行。每行包含一个整数，其中第 $ i$ 行的整数表示第 $ i$ 个操作的输出。
输入输出样例
输入样例：
10 10 1 2 11 3 13 2 5 3 7 2 8 2 10 2 11 3 14 2 18 4 9输出样例：
2 2 2 4 3 5 5 7 8 11数据范围与约定
对于 $ 100\%$ 的数据，$ 1\le n\le 10^8,\ 1\le m\le 10^5$。
输入保证对于所有的操作，$ x$ 必然已经出现在队列中，同时对于所有操作
1，$ 1\le y\le 2\times 10^8$，并且 $ y$ 没有出现在队列中。对于所有操作
4，保证 $ 1\le k\le n$。
题解：
平衡树”区间移动“题。
用带点分裂的 fhq Treap 移动区间，用线段树维护区间内元素在平衡树上的数组下标。
在平衡树上保留父亲信息。其中fa[root]=0 ，然后就可以顺着爬上去来计算每个节点的排名。
时间复杂度 $ O(m\log n)$。
Code：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define len(x) (r[x]-l[x]+1)
#define mid ((L+R)>>1)
#define N 200000000
namespace sgt
{
int ls[6000000],rs[6000000],v[6000000],lazy[6000000],pcnt=1;
void pushdown(int k,int L,int R)
{
if(!lazy[k]||L==R)
return;
int x=lazy[k];
v[ls[k]]=x;
lazy[ls[k]]=x;
v[rs[k]]=x;
lazy[rs[k]]=x;
lazy[k]=0;
return;
}
void change(int k,int l,int r,int L,int R,int x)//把区间[l,r]改成x
{
if(l<=L&&r>=R)
{
v[k]=x;
lazy[k]=x;
return;
}
if(r<L||l>R)
return;
if(!ls[k])
ls[k]=++pcnt;
if(!rs[k])
rs[k]=++pcnt;
pushdown(k,L,R);
change(ls[k],l,r,L,mid,x);
change(rs[k],l,r,mid+1,R,x);
}
int ask(int k,int p,int L,int R)//求点i的编号
{
if(!ls[k]&&!rs[k])
return v[k];
pushdown(k,L,R);
if(p<=mid)
return ask(ls[k],p,L,mid);
return ask(rs[k],p,mid+1,R);
}
}
int root=0;
namespace bst
{
int rdm[200100],ls[200100],rs[200100],fa[200100];
int sz[200100],l[200100],r[200100];
int pcnt=0;
int Newnode(int L,int R)
{
++pcnt;
l[pcnt]=L;
r[pcnt]=R;
sz[pcnt]=R-L+1;
rdm[pcnt]=rand();
sgt::change(1,L,R,1,N,pcnt);
return pcnt;
}
void maintain(int k)
{
sz[k]=sz[ls[k]]+sz[rs[k]]+r[k]-l[k]+1;
fa[ls[k]]=k;
fa[rs[k]]=k;
}
int Merge(int a,int b)
{
if(!a||!b)
return a|b;
if(rdm[a]<rdm[b])
{
rs[a]=Merge(rs[a],b);
maintain(a);
return a;
}
ls[b]=Merge(a,ls[b]);
maintain(b);
return b;
}
void split(int rt,int x,int &a,int &b)
{
if(!rt)
{
a=0,b=0;
return;
}
int L=sz[ls[rt]],R=r[rt]-l[rt]+1;
if(x<=L)
{
b=rt;
split(ls[rt],x,a,ls[b]);
}
else if(x<L+R)
{
x-=L;
a=rt;
b=Newnode(l[rt]+x,r[rt]);
r[a]=l[rt]+x-1;
rs[b]=rs[a];
rs[a]=0;
maintain(a);
maintain(b);
return;
}
else
{
a=rt;
split(rs[rt],x-L-R,rs[a],b);
}
maintain(rt);
}
int Rank(int p)
{
int k=sgt::ask(1,p,1,N);
int ans=sz[ls[k]]+p-l[k]+1;
while(fa[k])
{
if(k==rs[fa[k]])
ans+=sz[ls[fa[k]]]+len(fa[k]);
k=fa[k];
}
return ans;
}
}
int main()
{
int n,m,op,x,y,z=0;
int a,b,c;
scanf("%d%d",&n,&m);
root=bst::Newnode(1,n);
while(m--)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d%d",&x,&y);
x-=z,y-=z;
z=bst::Rank(x);
printf("%d\n",z);
bst::split(root,z-1,a,b);
bst::split(b,1,b,c);
bst::l[b]=bst::r[b]=y;
sgt::change(1,y,y,1,N,b);
root=bst::Merge(bst::Merge(a,b),c);
bst::fa[root]=0;
}
else if(op==2||op==3)
{
scanf("%d",&x);
x-=z;
z=bst::Rank(x);
printf("%d\n",z);
bst::split(root,z-1,a,b);
bst::split(b,1,b,c);
if(op==2)
root=bst::Merge(bst::Merge(b,a),c);
else
root=bst::Merge(bst::Merge(a,c),b);
bst::fa[root]=0;
}
else
{
scanf("%d",&x);
x-=z;
bst::split(root,x-1,a,b);
bst::split(b,1,b,c);
z=bst::l[b];
printf("%d\n",z);
root=bst::Merge(bst::Merge(a,b),c);
bst::fa[root]=0;
}
}
return 0;
}
说点什么