Insert(root,k,0); //再插入
Splay(tot,0); //旋转至根部,这步不加会TLE
}
int Get_Rank(int x){
int k=Bin(x);
int y=node[k];
Splay(y,0);
return size[ch[root][0]]+1;
}
int Get_Kth(int r,int k){
int t=size[ch[r][0]];
if(k<=t)
return Get_Kth(ch[r][0],k);
else if(k<=t+num[r])
return s[key[r]]+(k-t)-1;
else
return Get_Kth(ch[r][1],k-t-num[r]);
}
void slove(){
for(int i=0;i
Top(ope[i]);
else if(str[i][0]=='Q')
printf("%d\n",Get_Rank(ope[i]));
else
printf("%d\n",Get_Kth(root,ope[i]));
}
} www.2cto.com
int main(){
int t,cas=0;
scanf("%d",&t);
while(t--){
//将所有TOP和QUERY操作的点进行离散化，将中间不变的区间缩成点
int total=0;
p[total++]=0;
for(int i=0;i
if(str[i][0]=='T'||str[i][0]=='Q')
p[total++]=ope[i];
}
p[total++]=n;
sort(p,p+total);
cnt=0;
//进行离散化，s[i]表示区间起点，e[i]表示区间终点
for(int i=1;i
if(p[i]-p[i-1]>1){ //中间的区间
s[cnt]=p[i-1]+1;
e[cnt]=p[i]-1;
cnt++;
}
s[cnt]=p[i]; //端点
e[cnt]=p[i];
cnt++;
}
root=tot=0;
ch[root][0]=ch[root][1]=pre[root]=size[root]=num[root]=key[root]=0;
Bulid(root,0,cnt-1,0); //建树
printf("Case %d:\n",++cas);
slove();
}
return 0;
}
作者：ACM_cxlove