po3580SuperMemo（splay)

操作不少，不过都是一些基本的操作，增删，旋转，逆转，询问最小。
注意一点：T<0时让t=0；
旋转的时候，是顺时针旋转，数据范围在int内。
刚开始旋转转错方向了。。
 #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 long long

 #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>>;

 using namespace std;

 int a[N];

 struct splay_tree

 {

     int pre[N],size[N];

     int ch[N][];

     int root,tot;

     int lz2[N];

     LL s[N],lz1[N],key[N];

 //    void dfs(int x)

 //    {

 //        if(x)

 //        {

 //            dfs(ch[x][0]);

 //            printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size=%2d,key=%2d lz1 = %d lz2 = %d min = %d\n",

 //                   x,ch[x][0],ch[x][1],pre[x],size[x],key[x],lz1[x],lz2[x],s[x]);

 //            dfs(ch[x][1]);

 //        }

 //    }

 //    void debug()

 //    {

 //        printf("root:%d\n",root);

 //        dfs(root);

 //    }

 //以上用于debug*/

     void newnode(int &x,int v,int fa)//新建一结点

     {

         x = ++tot;

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

         pre[x] = fa;

         lz1[x] = lz2[x] = ;

         size[x] = ;

         s[x] = v;

         key[x] = v;

     }

     void pushdown(int w)

     {

         int l = ch[w][],r = ch[w][];

         if(lz1[w])

         {

             lz1[l] += lz1[w];

             lz1[r] += lz1[w];

             s[l]+=lz1[w];

             s[r]+=lz1[w];

             key[l]+=lz1[w];

             key[r]+=lz1[w];

             lz1[w] = ;

         }

         if(lz2[w])

         {

             lz2[l]^=lz2[w];

             lz2[r]^=lz2[w];

             swap(ch[w][],ch[w][]);

             lz2[w] = ;

         }

     }

     void pushup(int w)

     {

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

         s[w] = key[w];

         if(ch[w][])

             s[w] = min(s[w],s[ch[w][]]);

         if(ch[w][])

             s[w] = min(s[w],s[ch[w][]]);

     }

     void rotate(int r,int kind)

     {

         int y = pre[r];

         pushdown(y);

         pushdown(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)

     {

         pushdown(r);

         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;

         pushdown(r);

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

         {

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

                 r = ch[r][];

             else

             {

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

                 r = ch[r][];

             }

             pushdown(r);

         }

         return r;

     }

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

     {

         splay(get_k(l),);

         splay(get_k(r+),root);

         lz1[key_value]+=k;

         s[key_value]+=k;

         key[key_value]+=k;

         pushup(ch[root][]);

         pushup(root);

     }

     LL query(int l,int r)

     {

         splay(get_k(l),);

         splay(get_k(r+),root);

         return s[key_value];

     }

     void reverse(int l,int r)

     {

         splay(get_k(l),);

         splay(get_k(r+),root);

         lz2[key_value]^=;

         pushup(ch[root][]);

         pushup(root);

     }

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

     {

         splay(get_k(r-k+),);

         splay(get_k(r+),root);

         int nod = key_value;

         key_value = ;

         pushup(ch[root][]);

         pushup(root);

         splay(get_k(l),);

         splay(get_k(l+),root);

         key_value = nod;

         pre[nod] = ch[root][];

         pushup(ch[root][]);

         pushup(root);

     }

     void insert(int k,int p)

     {

         splay(get_k(k),);

         splay(get_k(k+),root);

         newnode(key_value,p,ch[root][]);

         pushup(ch[root][]);

         pushup(root);

     }

     void updelete(int k)

     {

         splay(get_k(k),);

         splay(get_k(k+),root);

         key_value = ;

         pushup(ch[root][]);

         pushup(root);

     }

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

     {

         int m = (l+r)>>;

         if(l>r) return ;

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

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

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

         pushup(x);

     }

     void init(int o)

     {

         int i;

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

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

         size[] = ch[][] = ch[][] =  key[] = lz1[] = lz2[] = s[] = ;

         root = tot = ;

         newnode(root,,);

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

         build(ch[ch[root][]][],,o,ch[root][]);

         size[root] = ;

         pushup(ch[root][]);

         pushup(root);

     }

 //    void work()

 //    {

 //        for(int i =  1; i <= size[root] ;i++)

 //        cout<<key[get_k(i)]<<" ";

 //        puts("");

 //    }

 } SP;

 int main()

 {

     int n,q,k,x,y;

     char sq[];

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

     {

         SP.init(n);

         scanf("%d",&q);

         while(q--)

         {

             scanf("%s",sq);

             if(sq[]=='A')

             {

                 scanf("%d%d%d",&x,&y,&k);

                 SP.add(x,y,k);

             }

             else if(strcmp(sq,"REVERSE")==)

             {

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

                 SP.reverse(x,y);

             }

             else if(strcmp(sq,"REVOLVE")==)

             {

                 scanf("%d%d%d",&x,&y,&k);

                 if(k<=) continue;

                 k = k%(y-x+);

                 SP.revolve(x,y,k);

             }

             else if(sq[]=='I')

             {

                 scanf("%d%d",&k,&x);

                 SP.insert(k+,x);

             }

             else if(sq[]=='D')

             {

                 scanf("%d",&k);

                 SP.updelete(k);

             }

             else if(sq[]=='M')

             {

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

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

             }

             //SP.work();

         }

     }

     return ;

 }
巴特西

po3580SuperMemo（splay)

最新文章

热门文章
