hdu1754(splay)

给n个数，有两种操作 Q a b 询问区间[a,b]的最大值， U a b 将第a个数的值改成b

splay树的中序遍历是我们所维护的序列。如果要询问区间[a,b]的最大值，那么只要将第a-1个数旋转到根结点，将第b+1个数旋转到根的右孩子，那么根的右孩子的左子树就是所要查询的区间。我们为每一个结点维护一个最大值，表示该以该结点为根的子树的最大值，那么答案就是 Max[next[next[root][1]][0]];

为了防止越界，比如要查询区间[1,n] 那么要将第0个数旋转到根结点，将第n+1个数旋转到根的右孩子，但是却没有这两个数。所以为了方便，在序列的两端加上两个数，这两个数比序列中的所有数都小，所以并不影响答案。

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <string.h>
  4 #include <algorithm>
  5 const int  N = 200000 + 10;
  6 int next[N][2],pre[N],key[N],Max[N],sz[N],tot,root;
  7 int a[N];
  8 
  9 //如果更新第x个结点， 那么将第该结点splay到根，然后更新
 10 /*
 11 如果询问区间[a,b]的最大值， 那么将a-1 splay到root，将b+1旋到next[root][1]
 12 
 13 */
 14 void newNode(int &rt, int fa, int k)
 15 {
 16     rt = ++tot;
 17     next[rt][0] = next[rt][1] = 0;
 18     sz[rt] = 1;
 19     pre[rt] = fa;
 20     key[rt] = k;
 21     Max[rt] = k;//???????
 22 }
 23 void maintain(int rt)
 24 {
 25     Max[rt] = std::max(key[rt], std::max(Max[next[rt][0]],Max[next[rt][1]]));
 26     sz[rt] = sz[next[rt][0]] + sz[next[rt][1]] + 1;
 27 }
 28 void build(int &rt, int fa, int l, int r)
 29 {
 30     if(l>r) return;
 31     int m =(l+r)>>1;
 32     newNode(rt,fa,a[m]);
 33     build(next[rt][0],rt,l,m-1);
 34     build(next[rt][1],rt,m+1,r);
 35     maintain(rt);
 36 }
 37 void rotate(int x, int kind)
 38 {
 39     int y = pre[x];
 40     next[y][!kind] = next[x][kind];
 41     maintain(y);
 42     pre[next[x][kind]] = y;
 43     if(pre[y])
 44         next[pre[y]][next[pre[y]][1]==y] = x;
 45     pre[x] = pre[y];
 46     next[x][kind] = y;
 47     pre[y] = x;
 48     maintain(x);
 49 }
 50 int kth(int x, int k)
 51 {
 52     int tmp = sz[next[x][0]] + 1;
 53     if(tmp==k)
 54         return x;
 55     if(tmp > k)
 56         return kth(next[x][0],k);
 57     return kth(next[x][1],k-tmp);
 58 }
 59 void splay(int x, int goal)
 60 {
 61     /*
 62     只考虑左右旋的splay
 63     while(pre[x]!=goal)
 64     {
 65         if(next[pre[x]][0]==x)
 66             rotate(x,1);
 67         else
 68             rotate(x,0);
 69     }
 70     */
 71     while(pre[x]!=goal)
 72     {
 73         int y = pre[x];
 74         if(pre[y]==goal)
 75         {
 76             if(next[y][0]==x)
 77                 rotate(x,1);
 78             else
 79                 rotate(x,0);
 80         }
 81         else
 82         {
 83              //kind 表示y是父亲的哪个儿子, 0 左，1 右
 84             int kind = next[pre[y]][1]==y;
 85             if(next[y][kind]==x)//共线
 86             {
 87                 rotate(y,!kind);
 88                 rotate(x,!kind);
 89             }
 90             else
 91             {
 92                 rotate(x,kind);
 93                 rotate(x,!kind);
 94             }
 95         }
 96     }
 97     if(goal==0)
 98         root = x;
 99 }
100 int main()
101 {
102     int n,m;
103     char opt[3];
104     int x,y;
105     while(scanf("%d%d",&n,&m)!=EOF)
106     {
107         tot = 0;
108         memset(next,0,sizeof(next));
109         for(int i=1;i<=n;++i)
110             scanf("%d",&a[i]);
111         newNode(root,0,-1);
112         newNode(next[root][1],root,-2);
113         build(next[next[root][1]][0],next[root][1],1,n);
114         maintain(next[root][1]);
115         maintain(root);
116         while(m--)
117         {
118             scanf("%s%d%d",opt,&x,&y);
119             if(opt[0]=='Q')
120             {
121                 int tmp = kth(root,x);
122                 splay(tmp,0);
123                 splay(kth(root,y+2),root);
124                 printf("%d
",Max[next[next[root][1]][0]]);
125             }
126             else
127             {
128                 splay(kth(root,x+1),0);
129                 key[root] = Max[root] = y;
130                 maintain(root);
131             }
132         }
133     }
134     return 0;
135 }