题意：定义3种操作

1 x y 把编号为x，权值为y的人加入队列

2 询问权值最大的人的编号

3 询问权值最小的人的编号

 

思路：(1) Splay

　　   (2) STL set

1 #include
     
         2 using namespace std;   3 #define MAXN 1000001   4 struct node   5 {
     6     int left,right,father;   7     int key;   8     int leftnum,rightnum;   9 };  10 node tree[MAXN];  11 int root=0;  12 void update(int x)  13 {
    14     if(x!=0)  15     {
    16         if(tree[x].left!=0) tree[x].leftnum=tree[tree[x].left].leftnum;  17         else tree[x].leftnum=x;  18         if(tree[x].right!=0) tree[x].rightnum=tree[tree[x].right].rightnum;  19         else tree[x].rightnum=x;  20     }  21 }  22  23 void leftrotate(int x)  24 {
    25     int y=tree[x].father;  26     int z=tree[x].left;  27     if(y==tree[tree[y].father].left) tree[tree[y].father].left=x;  28     else tree[tree[y].father].right=x;  29     tree[x].father=tree[y].father;  30     tree[x].left=y;  31     tree[y].father=x;  32     tree[y].right=z;  33     tree[z].father=y;  34     update(z);  35     update(y);  36     update(x);  37 }  38  39 void rightrotate(int x)  40 {
    41     int y=tree[x].father;  42     int z=tree[x].right;  43     if(y==tree[tree[y].father].right) tree[tree[y].father].right=x;  44     else tree[tree[y].father].left=x;  45     tree[x].father=tree[y].father;  46     tree[x].right=y;  47     tree[y].father=x;  48     tree[y].left=z;  49     tree[z].father=y;  50     update(z);  51     update(y);  52     update(x);  53 }  54  55 void splay(int x)  56 {
    57     int y,z;  58     while(tree[x].father!=0)  59     {
    60         y=tree[x].father;  61         z=tree[y].father;  62         if(z==0)  63         {
    64             if(x==tree[y].left) rightrotate(x);  65             else leftrotate(x);  66             break;  67         }  68         if(y==tree[z].left)  69         {
    70             if(x==tree[y].left)  71             {
    72                 rightrotate(y); rightrotate(x);  73             }  74             else  75             {
    76                 leftrotate(x); rightrotate(x);  77             }  78         }  79         else  80         {
    81             if(x==tree[y].left)  82             {
    83                 rightrotate(x); leftrotate(x);  84             }  85             else  86             {
    87                 leftrotate(y); leftrotate(x);  88             }  89         }  90     }  91     root=x;  92 }             93 void insert(int x,int y,int i)  94 {
    95     if(root==0)  96     {
    97         root=x;  98         tree[x].leftnum=tree[x].rightnum=tree[x].father=tree[x].left=tree[x].right=0;  99         update(x); 100         tree[x].key=y; return ; 101     } 102     if(y<=tree[i].key) 103     {
   104         if(tree[i].left==0) 105         {
   106             tree[i].left=x; 107             tree[x].leftnum=tree[x].rightnum=tree[x].left=tree[x].right=0; tree[x].father=i; 108             tree[x].key=y; 109             splay(x); 110             return ; 111         } 112         else insert(x,y,tree[i].left); 113     } 114     else 115     {
   116         if(tree[i].right==0) 117         {
   118             tree[i].right=x; 119             tree[x].leftnum=tree[x].rightnum=tree[x].left=tree[x].right=0; tree[x].father=i; 120             tree[x].key=y; 121             splay(x); 122             return ; 123         } 124         else insert(x,y,tree[i].right); 125     } 126 } 127 void del(int x,bool w) 128 {
   129     int y=tree[x].father; 130     if(w==1) 131     {
   132         tree[y].left=tree[x].right; 133         tree[tree[x].right].father=y; 134         update(y); 135         if(root==x) root=tree[x].right; 136         else splay(y); 137     } 138     else 139     {
   140         tree[y].right=tree[x].left; 141         tree[tree[x].left].father=y; 142         update(y); 143         if(root==x) root=tree[x].left; 144         else splay(y); 145     } 146 } 147 int main() 148 {
   149     node a; 150     int x,y,z; 151     scanf("%d",&x); 152     while(x!=0) 153     {
   154         if(x==1) 155         {
   156             scanf("%d%d",&y,&z); 157             insert(y,z,root); 158         } 159         if(x==2) 160         {
   161             if(root==0) printf("0\n"); 162             else 163             {
   164                 y=tree[root].rightnum; 165                 printf("%d\n",y); 166                 del(y,0); 167             } 168           169         } 170         if(x==3) 171         {
   172             if(root==0) printf("0\n"); 173             else 174             {
   175                 y=tree[root].leftnum; 176                 printf("%d\n",y); 177                 del(y,1); 178             } 179           180         } 181         scanf("%d",&x); 182     } 183     return 0; 184 }
     

1 #include
     
        2 #include
      
         3 using namespace std;  4 struct node  5 {
    6     int key,num;  7 };  8 bool operator <(const node &x,const node &y)  9 {
   10     return x.key
       
         tree; 13 int main() 14 {
   15     node a; 16     int x; 17     scanf("%d",&x); 18     while(x!=0) 19     {
   20         if(x==1) 21         {
   22             scanf("%d%d",&a.num,&a.key); 23             tree.insert(a); 24         } 25         if(x==2) 26         {
   27             if(tree.empty())printf("0\n"); 28             else 29             {
   30                 a=*tree.rbegin(); 31                 printf("%d\n",a.num); 32                 tree.erase(a); 33             } 34         } 35         if(x==3) 36         {
   37             if(tree.empty())printf("0\n"); 38             else 39             {
   40                 printf("%d\n",tree.begin()->num); 41                 a=*tree.begin(); 42                 tree.erase(a); 43             } 44         } 45         scanf("%d",&x); 46     } 47     return 0; 48 } 49