hdu1754I Hate It(splay)

线段树的水题，拿来学习一下splay.

本题涉及到求最大值以及单点更新，折腾了许久，差不多把splay搞明白了。

按位置建树，按位置是一颗排序二叉树，对于区间的操作非常方便，每次操作都将需要的结点转自根的右孩子的左孩子，因为加了2个结点，一个最小的，一个最大的，据说是为了防止越界。

这题只有单点，所以每次将所求结点旋自根节点即可。

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 #include<cmath>

 #include<queue>

 #include<set>

 using namespace std;

 #define N 200010

 #define LL __int64

 #define INF 0xfffffff

 #define key_value ch[ch[root][1]][0]

 const double eps = 1e-;

 const double pi = acos(-1.0);

 const double inf = ~0u>>;

 int pre[N],s[N],size[N];

 int ch[N][],a[N],val[N];

 int root,n,tot;

 void newnode(int &x,int k,int fa)

 {

     x = ++tot;

     ch[x][]=ch[x][] = ;

     pre[x] = fa;

     size[x] = ;

     s[x] = k;

     val[x] = k;

 }

 void pushup(int w)

 {

     size[w] = size[ch[w][]]+size[ch[w][]]+;

     s[w] = max(max(s[ch[w][]],s[ch[w][]]),val[w]);

    // cout<<s[w]<<" "<<w<<"// "<<" "<<ch[w][1]<<" "<<s[w]<<endl;

 }

 void rotate(int r,int kind)

 {

     int y = pre[r];

     ch[y][!kind] = ch[r][kind];

     pre[ch[r][kind]] = y;

     if(pre[y])

     {

         ch[pre[y]][ch[pre[y]][]==y] = r;

     }

     pre[r] = pre[y];

     ch[r][kind] = y;

     pre[y] = r;

     pushup(y);

     //pushup(r);

 }

 void splay(int r,int goal)

 {

     while(pre[r]!=goal)

     {

        if(pre[pre[r]]==goal)

         {

              rotate(r,ch[pre[r]][]==r);

         }

         else

         {

             int y = pre[r];

             int kind = (ch[pre[y]][]==y);

             if(ch[y][kind]==r)

             {

                 rotate(r,!kind);

                 rotate(r,kind);

             }

             else

             {

                 rotate(y,kind);

                 rotate(r,kind);

             }

         }

     }

     pushup(r);

     if(goal==) root = r;

 }

 int get_k(int k)

 {

     int r = root;

     while(size[ch[r][]]!=k)

     {

         if(size[ch[r][]]>k)

         r = ch[r][];

         else

         {

             k-=(size[ch[r][]]+);

             r = ch[r][];

         }

     }

     return r;

 }

 int query(int l,int r)

 {

     splay(get_k(l-),);

     splay(get_k(r+),root);

     return s[key_value];

 }

 /*void update(int l,int r,int k)

 {

     splay(get_k(l-1),0);

     splay(get_k(r+1),root);

     val[key_value] = k;

     s[key_value] = k;

     pushup(ch[root][1]);

     pushup(root);

 }*/

 void update(int l,int r,int k)

 {

     int kk = get_k(l);

     val[kk] = k;

     splay(kk,);

 }

 void build(int &w,int l,int r,int fa)

 {

     if(l>r) return ;

     int m = (l+r)>>;

     newnode(w,a[m],fa);

     build(ch[w][],l,m-,w);

     build(ch[w][],m+,r,w);

     pushup(w);

 }

 void init()

 {

     int i;

     for(i =  ;i < n ;i++)

     scanf("%d",&a[i]);

     ch[][] = ch[][] = pre[] = size[] = s[] = ;

     root = tot =;

     newnode(root,-,);

     newnode(ch[root][],-,root);

     size[root] = ;

     build(key_value,,n-,ch[root][]);

     pushup(ch[root][]);

     pushup(root);

 }

 int main()

 {

     int q,x,y,i;

     char sq[];

     while(scanf("%d%d",&n,&q)!=EOF)

     {

         init();

         while(q--)

         {

             scanf("%s%d%d",sq,&x,&y);

             if(sq[]=='U')

             {

                 update(x,x,y);

                 /*for(i = 0; i <= n+2; i++)

                 cout<<ch[i][0]<<" "<<ch[i][1]<<" "<<i<<endl;

                 puts("");*/

             }

             else

             {

                 printf("%d\n",query(x,y));

                 /*for(i = 0; i <= n+2; i++)

                 cout<<ch[i][0]<<" "<<ch[i][1]<<" "<<i<<endl;

                 puts("");*/

             }

         }

     }

     return ;

 }

巴特西

hdu1754I Hate It(splay)

最新文章

热门文章