【题目大意】
一开始给定n个人，他们按编号1..n地排好了。
有3个操作。
分别是：
Top x：把编号为x个人放到a[1]。然后a[1..x-1]的数都向后移一位。
Query x：返回编号为x个人现在在哪里位置。
Rank x：返回排名在x的这个人是编号是多少？
【算法分析】
我采用的是Splay来离线解决。
由于n高达10^8。所以不能完全模拟。
首先是把询问都读进来，然后对于Top和Query碰到的编号，开一个List取出来，排序并去重。
然后开始构建Splay。
对于在List中的编号，我们把他构建成一个结点。
然后对于List[i]和List[i-1]之间的间隙结点，我把它们都压缩成一个结点。（当然Size的计算方法就有点不同了。）
然后这样，Splay上最多有2*Q个点了。
对于Top操作，我们就相当于删掉这个点，再插入一次这个点。
对于Query，我们可以直接把这个点Splay到根，然后算他的左子树的Size，+1就是答案。
对于Rank，我们就像找第k个元素那样，找到那个对应位置，输出就行了。（就是压缩块有点不同而已）
【其它】
2TLE。写惯了SBT。。。那个父亲的域老是忘了维护，导致死循环了。
【CODE】
#include #include #include struct Splay_t{ int cmp(const void *A,const void *B){return *((int*)A) – *((int*)B);} void pre_Insert(){ int Find(int x){ void solve(){ int main(){
const int N=305555;
int root,tot,Lasttop;
int ch[N][2],pre[N];
struct Node{int St,Size,weight;}Tr[N];
void init(){
root=tot=1;
Lasttop=2;
ch[1][0]=ch[1][1]=0;
Tr[0].Size=0;
pre[1]=0;
}
void rotate(int x,int T){
int y=pre[x];
if (T){
ch[y][0]=ch[x][1];
ch[x][1]=y;
pre[ch[y][0]]=y;
pre[x]=pre[y];
pre[y]=x;
}
else{
ch[y][1]=ch[x][0];
ch[x][0]=y;
pre[ch[y][1]]=y;
pre[x]=pre[y];
pre[y]=x;
}
if (ch[pre[x]][0]==y) ch[pre[x]][0]=x;
else ch[pre[x]][1]=x;
update(y);
update(x);
}
void Splay(int x,int cut){
if (x==cut) return;
int y,z;
while (pre[x]!=cut){
y=pre[x]; z=pre[y];
if (z==cut) rotate(x,ch[y][0]==x);
else
if (ch[z][0]==y)
if (ch[y][0]==x) {rotate(y,1); rotate(x,1);}
else {rotate(x,0); rotate(x,1);}
else
if (ch[y][1]==x) {rotate(y,0); rotate(x,0);}
else {rotate(x,1); rotate(x,0);}
}
}
void Ins(int St,int weight){
tot++;
ch[tot][0]=ch[tot][1]=0;
Tr[tot].St=St;
Tr[tot].weight=Tr[tot].Size=weight;
if (tot==2){
ch[root][0]=2;
pre[2]=root;
}
else{
Splay(tot-1,root);
ch[tot-1][1]=tot;
update(tot-1);
pre[tot]=tot-1;
}
Splay(tot,root);
}
void Top(int x){
if (Lasttop==x) return;
Splay(x,root);
int p,q;
q=x; p=ch[x][1];
while (p){
q=p;
p=ch[p][0];
}
if (q==x){
ch[1][0]=ch[x][0];
pre[ch[x][0]]=1;
}
else{
Splay(q,x);
ch[q][0]=ch[x][0];
pre[q]=1;
pre[ch[x][0]]=q;
ch[1][0]=q;
update(q);
}
Splay(Lasttop,root);
ch[Lasttop][0]=x;
pre[x]=Lasttop;
ch[x][0]=ch[x][1]=0;
update(x);
update(Lasttop);
Lasttop=x;
}
int Query(int x){
Splay(x,root);
return Tr[ch[x][0]].Size+1;
}
int rank(int x){
int p,done=0;
p=ch[root][0];
while (1){
if (x<=Tr[ch[p][0]].Size+done)
p=ch[p][0];
else
if (x>Tr[ch[p][0]].Size+done+Tr[p].weight){
done+=Tr[ch[p][0]].Size+Tr[p].weight;
p=ch[p][1];
}
else break;
}
Splay(p,root);
return x-Tr[ch[p][0]].Size+Tr[p].St-1;
}
}Splay;
int n,Q,Lt;
int op[N],a[N],List[N],pos[N];
void init(){
int i,cnt;
Lt=List[0]=0;
char Str[100];
scanf("%d%d",&n,&Q);
for (i=1;i<=Q;i++){
scanf("%s%d",Str,&a[i]);
switch (Str[0]){
case ‘T’:op[i]=1; break;
case ‘Q’:op[i]=2; break;
case ‘R’:op[i]=3; break;
}
if (op[i]!=3) List[++Lt]=a[i];
}
qsort(List+1,Lt,sizeof(int),cmp);
for (i=1,cnt=0;i<=Lt;i++){
cnt+=(!cnt || List[i]!=List[cnt]);
List[cnt]=List[i];
}
Lt=cnt;
}
int i;
Splay.init();
for (List[0]=0,i=1;i<=Lt;i++){
if (List[i]-List[i-1]>1)
Splay.Ins(List[i-1]+1,List[i]-List[i-1]-1);
Splay.Ins(List[i],1);
pos[i]=Splay.tot;
}
}
int l=1,r=Lt,mid;
while (l
if (x>List[mid]) l=mid+1;
else r=mid;
}
return pos[l];
}
int i;
for (i=1;i<=Q;i++)
switch (op[i]){
case 1:Splay.Top(Find(a[i])); break;
case 2:printf("%dn",Splay.Query(Find(a[i]))); break;
case 3:
if (a[i]>List[Lt]) printf("%dn",a[i]);
else printf("%dn",Splay.rank(a[i]));
break;
}
}
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
printf("Case %d:n",i);
init();
pre_Insert();
solve();
}
}
帅呆了