FZU 2100(排队-Treap维护队列最大值)
Problem Description Input Output Sample Input Sample Output SourceFOJ有奖月赛-2012年11月
这题因为把转移中的maxv打成v而Wa了一天（一天啊！）言归正传，这题是要维护平衡树子树最大值，Treap的rotate是参考刘汝佳的写法。就是insert时要根据左右子树的s(size)和maxv比大小

#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<functional>#include<algorithm>using namespace std;#define MAXN (100000+10)int t,n;struct node{int v,r,s,maxv,i;node *ch[2];node(int _v,int _i):s(1),r(rand()),v(_v),maxv(_v),i(_i){ch[0]=ch[1]=NULL;}bool operator<(const node &b){return r<b.r;}void maintain(){s=1;maxv=v;if (ch[0]!=NULL) {s+=ch[0]->s;maxv=max(maxv,ch[0]->maxv);} if (ch[1]!=NULL) {s+=ch[1]->s;maxv=max(maxv,ch[1]->maxv);}}}*root=NULL;void rotate(node *&o,int d){node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o;o->maintain();k->maintain();o=k;}void del(node *&o){if (o==NULL) return;del(o->ch[0]);del(o->ch[1]);delete o;o=NULL;}bool flag=1;void print(node *&o){if (o->ch[0]!=NULL) print(o->ch[0]);if (flag) printf(" ");else flag=1;printf("%d",o->i);if (o->ch[1]!=NULL) print(o->ch[1]);}void insert(node *&o,int x,int k,int i){if (o==NULL){o=new node(x,i);return;}int d;if (o->ch[1]==NULL) {if (k&&o->v<x) d=0;else d=1;}else if (o->ch[1]->s>=k||o->ch[1]->maxv>x||o->v>x) d=1;else d=0;if (d==0){if (o->ch[1]!=NULL) k-=o->ch[1]->s;k--;}insert(o->ch[d],x,k,i);o->maintain();if (o->ch[d]<o) rotate(o,d^1);o->maintain();}int main(){//freopen("fzu2100.in","r",stdin);//freopen("fzu2100.out","w",stdout);scanf("%d",&t);while (t--){del(root);root=NULL;scanf("%d",&n);for (int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);insert(root,x,y,i);}flag=0;print(root);printf("\n");}return 0;}