写平衡树修锅快修到死系列
我太蠢了
其实是平衡树裸体裸题
插入，删除，交换前驱或后继，查询rank和kth
维护一个pos数组，表示第i个书的编号
然后注意许许多多的细节，没了
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct Node{
int lson,rson,ran,val,w,sz;
}Treap[80000<<2];
int pos[80100],Lx,Rx,Nodecnt,n,m,root;
void pushup(int o){
Treap[o].sz=Treap[Treap[o].lson].sz+Treap[Treap[o].rson].sz+1;
}
void rotateR(int &o){
int k=Treap[o].lson;
Treap[o].lson=Treap[k].rson;
Treap[k].rson=o;
Treap[k].sz=Treap[o].sz;
pushup(o);
o=k;
}
void rotateL(int &o){
int k=Treap[o].rson;
Treap[o].rson=Treap[k].lson;
Treap[k].lson=o;
Treap[k].sz=Treap[o].sz;
pushup(o);
o=k;
}
int NewNode(int cx,int wl){
++Nodecnt;
Treap[Nodecnt].sz=1;
Treap[Nodecnt].lson=Treap[Nodecnt].rson=0;
Treap[Nodecnt].ran=rand();
Treap[Nodecnt].val=wl;
Treap[Nodecnt].w=cx;
return Nodecnt;
}
void insert(int &o,int cx,int wl){
if(!o){
o=NewNode(cx,wl);
return;
}
Treap[o].sz++;
if(wl<=Treap[o].val){
insert(Treap[o].lson,cx,wl);
if(Treap[Treap[o].lson].ran<Treap[o].ran)
rotateR(o);
// pushup(o);
}
else{
insert(Treap[o].rson,cx,wl);
if(Treap[Treap[o].rson].ran<Treap[o].ran)
rotateL(o);
// pushup(o);
}
}
void erase(int &o,int wl){
if(!o)
return;
if(Treap[o].val==wl){
if(Treap[o].lson==0||Treap[o].rson==0){
o=Treap[o].lson+Treap[o].rson;
return;
}
if(Treap[Treap[o].lson].ran<Treap[Treap[o].rson].ran){
rotateR(o);
erase(o,wl);
}
else{
rotateL(o);
erase(o,wl);
}
pushup(o);
return;
}
Treap[o].sz--;
if(wl<=Treap[o].val){
erase(Treap[o].lson,wl);
pushup(o);
}
else{
erase(Treap[o].rson,wl);
pushup(o);
}
}
int ranks(int o,int wl){
if(!o)
return 0;
if(wl==Treap[o].val){
return Treap[Treap[o].lson].sz+1;
}
if(wl<=Treap[o].val){
return ranks(Treap[o].lson,wl);
}
else{
return ranks(Treap[o].rson,wl)+Treap[Treap[o].lson].sz+1;
}
}
int kth(int k,int o){
if(k==0)
return 0;
if(k==Treap[Treap[o].lson].sz+1)
return Treap[o].w;
if(k<=Treap[Treap[o].lson].sz)
return kth(k,Treap[o].lson);
else
return kth(k-Treap[Treap[o].lson].sz-1,Treap[o].rson);
}
int pre(int wl){
return kth(ranks(root,wl)-1,root);
}
int back(int wl){
return kth(ranks(root,wl)+1,root);
}
int main(){
Lx=1;
// freopen("7.in","r",stdin);
// freopen("test.out","w",stdout);
srand(19260817);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
++Rx;
pos[x]=Rx;
insert(root,x,Rx);
}
char opt[20];
int sx,tx;
for(int i=1;i<=m;i++){
scanf("%s",opt);
if(opt[0]=='T'){
scanf("%d",&sx);
erase(root,pos[sx]);
Lx--;
pos[sx]=Lx;
insert(root,sx,Lx);
}
else if(opt[0]=='B'){
scanf("%d",&sx);
erase(root,pos[sx]);
Rx++;
pos[sx]=Rx;
insert(root,sx,Rx);
}
else if(opt[0]=='I'){
scanf("%d %d",&sx,&tx);
if(tx==0)
continue;
if(tx==1){
int need=back(pos[sx]);
erase(root,pos[sx]);
erase(root,pos[need]);
swap(pos[sx],pos[need]);
insert(root,sx,pos[sx]);
insert(root,need,pos[need]);
}
if(tx==-1){
int need=pre(pos[sx]);
erase(root,pos[sx]);
erase(root,pos[need]);
swap(pos[sx],pos[need]);
insert(root,sx,pos[sx]);
insert(root,need,pos[need]);
}
}
else if(opt[0]=='A'){
scanf("%d",&sx);
printf("%d\n",ranks(root,pos[sx])-1);
}
else if(opt[0]=='Q'){
scanf("%d",&sx);
printf("%d\n",kth(sx,root));
}
}
return 0;
}