用伸展树模拟插队比线段树快乐3倍。。
但是pojT了。别的oj可以过，直接贴代码.
每次更新时，找到第pos个人，splay到根，然后作为新root的左子树即可
#include#include #include #include #define maxn 200005using namespace std;int pre[maxn],ch[maxn][2],num[maxn],key[maxn],size[maxn],tot,root;void init(){ tot=root=0; pre[root]=ch[root][1]=ch[root][0]=num[root]=key[root]=size[root]=0;}void newnode(int &r,int fa,int k,int val){ r=++tot; ch[r][0]=ch[r][1]=0; num[r]=val; key[r]=k; pre[r]=fa; size[root]=1;}void pushup(int r){ size[r]=size[ch[r][0]]+size[ch[r][1]]+1;}void rotate(int x,int kind){ int fa=pre[x]; ch[fa][!kind]=ch[x][kind]; pre[ch[x][kind]]=fa; if(pre[fa]) ch[pre[fa]][ch[pre[fa]][1]==fa]=x; pre[x]=pre[fa]; pre[fa]=x; ch[x][kind]=fa; pushup(x);pushup(fa);}void splay(int r,int goal){ while(pre[r]!=goal){ if(pre[pre[r]]==goal) rotate(r,ch[pre[r]][0]==r); else { int fa=pre[r]; int kind=ch[pre[fa]][0]==fa;//???????? if(ch[fa][kind]==r){ rotate(r,!kind); rotate(r,kind); } else { rotate(fa,kind); rotate(r,kind); } } } if(goal==0) root=r; pushup(r);pushup(root);}void Treavel(int x){ if(x) { Treavel(ch[x][0]); printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,key=%2d \n",x,ch[x][0],ch[x][1],pre[x],size[x],key[x]); Treavel(ch[x][1]); }}void debug(){ printf("root:%d\n",root); Treavel(root);}void Treval(int r){ if(r){ if(ch[r][0]) Treval(ch[r][0]); printf("%d ",num[r]); if(ch[r][1]) Treval(ch[r][1]); }}void getth(int pos){ int r=root; while(size[ch[r][0]]+1!=pos){ if(size[ch[r][0]]+1