http://acm.hdu.edu.cn/showproblem.php?pid=3436
题意:初始排列1到N,现在要你实现3种操作:
将x插入到队头去
询问x当前的位置
询问第x个位置上当前是谁.
分析:
下面用SplayTree来实现.不过依然要明白SplayTree提供的是N个房间,第i号房间里放的就是第i个人,各种操作不会变化房间的内容,变得只是房间之间的相对父子关系而已.
SplayTree需要 size,pre,ch 3种信息即可.
首先将1到n建立SPlayTree.
我们将根root节点的右儿子的左儿子位置称为关键位置.
对于top x操作:由于第x个人在x号房间里,先将x号房间旋转到根,删除根,在将最小的节点旋转到根,然后用x号房间替换最小的节点称为根.
对于Query x操作:直接将x+1号房间转到根节点,返回它左子树儿子个数即可.
对于Rank x 操作:直接用Get_Kth即可实现,找到第x+1位置的房间号.
不过这道题的N<=10^8,但是Q<=10^5,所以需要将数据离散化,对于所有top x命令,我们将所有区间离散化,然后依然第i个房间放的是顺序第i个区间,SplayTree的size数组表示节点r为根的树中所有区间包含的整数个数,num数组表示节点r(仅仅r节点)表示的区间所包含的数总数,也就是顺序第r个区间包含的数的总数.
AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=+;
int N,Q,T;
int s[maxn],e[maxn],cnt;//表示区间
int p[maxn];//提取出来的单点数
char op[maxn][];//命令
int qnum[maxn];//命令参数
int bin(int x)
{
int l=,r=cnt;
while(l<=r)
{
int mid=(l+r)>>;
if(s[mid]<=x && x<=e[mid])
return mid;
else if(x< s[mid])
r=mid-;
else
l=mid+;
}
return -;
} int size[maxn];
int num[maxn];
int pre[maxn];
int ch[maxn][],root; void Treavel(int x)
{
if(x)
{
Treavel(ch[x][]); printf("节点 %2d: 左儿子 %2d 右儿子 %2d ",x,ch[x][],ch[x][]);
printf("size %2d num %2d pre %2d s %2d e %2d\n",size[x],num[x],pre[x],s[x],e[x]); Treavel(ch[x][]);
}
}
void DeBug()
{
printf("root:%d\n",root);
Treavel(root);
}
void Push_Up(int r)
{
size[r] = size[ch[r][]]+size[ch[r][]]+num[r];
}
void Rotate(int x,int kind)
{
int y=pre[x];
ch[y][kind^] = ch[x][kind];
pre[ch[x][kind]] = y;
if(pre[y])
ch[pre[y]][ch[pre[y]][] == y] = x;
pre[x]=pre[y];
ch[x][kind]=y;
pre[y]=x;
Push_Up(y);
} void Splay(int r,int goal)
{
while(pre[r]!=goal)
{
if(pre[pre[r]]==goal)
Rotate(r,ch[pre[r]][]==r);
else
{
int y=pre[r];
int kind=ch[pre[y]][] == y;
if(ch[y][kind] == r)
{
Rotate(r,kind^);
Rotate(r,kind);
}
else
{
Rotate(y,kind);
Rotate(r,kind);
}
}
}
Push_Up(r);
if(goal==)
root=r;
}
void New_Node(int &r,int fa,int k)
{
r=k;
num[r]=size[r]=e[k]-s[k]+;
pre[r]=fa;
ch[r][]=ch[r][]=;
}
void Build(int &x,int l,int r,int fa)
{
if(l>r)
return;
int mid=(l+r)>>;
New_Node(x,fa,mid);
Build(ch[x][],l,mid-,x);
Build(ch[x][],mid+,r,x);
Push_Up(x);
}
void init()
{
root=;
pre[root]=;
ch[root][]=ch[root][]=;
size[root]=;
num[root]=;
Build(root,,cnt,);
}
int Get_Min(int r)
{
while(ch[r][]) r=ch[r][];
return r;
} //删除树根
void Delete()
{
if(ch[root][]== || ch[root][]==)
{
root = ch[root][]+ch[root][];
pre[root]=;
return ;
}
int k=Get_Min(ch[root][]);
Splay(k,root);
ch[k][]=ch[root][];
pre[ch[root][]]=k;
root=k;
pre[k]=;
Push_Up(root);
}
void Top(int x)
{
int r=bin(x);
Splay(r,);
Delete();
Splay(Get_Min(root),);
ch[r][]=;
ch[r][]=root;
pre[r]=;
pre[root]=r;
root=r;
Push_Up(r);
}
int Query(int x)
{
int r=bin(x);
Splay(r,);
return size[ch[r][]]+x-s[r]+;
}
int Rank(int x)
{
int r=root;
while()
{
//size[r]我之前写成了N,一直WA
if(size[ch[r][]] < x && size[r]-size[ch[r][]] >= x)
return s[r]-+x-size[ch[r][]];
else if(x<=size[ch[r][]])
r=ch[r][];
else
{
//这里的顺序千万别写反了,而且size[r]我之前写成了N,一直WA
x-=size[r]-size[ch[r][]];
r=ch[r][];
}
}
} //和上面那个Rank函数一样的功能,两个二选一,用一个即可
int Get_Rank(int r,int k)
{
int t = size[ch[r][]];
if(k <= t)
return Get_Rank(ch[r][],k);
else if(k <= t + num[r])
return s[r] + k - t - ;
else
return Get_Rank(ch[r][],k-t-num[r]);
} int main()
{
scanf("%d",&T);
for(int kase=;kase<=T;kase++)
{
scanf("%d%d",&N,&Q); int t=;
for(int i=;i<=Q;i++)
{
scanf("%s%d",op[i],&qnum[i]);
if(op[i][]=='T')
p[t++]=qnum[i];
}
p[t++]=;
p[t++]=N;
sort(p,p+t);
t=unique(p,p+t)-p;
cnt=;
for(int i=;i<t;i++)
{
if(i> && p[i]>p[i-]+)
{
cnt++;
s[cnt]=p[i-]+;
e[cnt]=p[i]-;
}
cnt++;
s[cnt]=e[cnt]=p[i];
}
init();
printf("Case %d:\n",kase);
for(int i=;i<=Q;i++)
{
if(i==)
{
int x=;
int y=;
}
if(op[i][]=='T')
Top(qnum[i]);
else if(op[i][]=='Q')
printf("%d\n",Query(qnum[i]));
else if(op[i][]=='R')
printf("%d\n",Rank(qnum[i]));
}
}
return ;
}