POJ 3580 SuperMemo(伸展树的几个基本操作)

题意：

给定一个数组，对数组进行6种操作。

区间加，区间翻转，插入一个值，删除一个值，区间求最小值。

区间循环移位。

题解：

前5种属于伸展树的基本操作，区间循环移位需要转化成基本操作：

区间[l,r]循环右移T位(T=T%(r-l+1) )。相当于区间[l,r-T]和区间[r-T+1,r] 

调换了位置。通过区间删除和插入可以完成。

  注意：删除操作需要有内存回收。

 

 

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ddd puts("111");
using namespace std;

#define keyv ch[ch[root][1]][0]
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 99;

int pre[maxn],sz[maxn],ch[maxn][2],addv[maxn],minv[maxn],key[maxn],rev[maxn],root,tot1;
int s[maxn],tot2;///内存池，当有删除操作的时候进行回收
int a[maxn];
int n,q;

void update_add(int r,int add)
{
    if(r==0)return;
    key[r] += add;
    minv[r] += add;
    addv[r] += add;
}

void update_rev(int r)
{
    if(r == 0)return;
    swap(ch[r][0],ch[r][1]);
    rev[r]^=1;///下面的反转次数+1。
}

void pushdown(int r)
{
    if(rev[r])
    {
        update_rev(ch[r][0]);
        update_rev(ch[r][1]);
        rev[r] = 0;
    }
    if(addv[r])
    {
        update_add(ch[r][0],addv[r]);
        update_add(ch[r][1],addv[r]);
        addv[r] = 0;
    }
}

void pushup(int r)
{
    sz[r] = 1 + sz[ch[r][0]]+sz[ch[r][1] ];
    minv[r] = key[r];
    if(ch[r][0])minv[r] = min(minv[r],minv[ch[r][0]]);
    if(ch[r][1])minv[r] = min(minv[r],minv[ch[r][1]]);

}
void newnode(int &r,int fa,int k)
{
    if(tot2)r = s[tot2--];
    else r = ++tot1;
    minv[r] = key[r] = k;
    pre[r] = fa;
    rev[r] = addv[r] = ch[r][0] = ch[r][1] = 0;
    sz[r] = 1;
}


void build(int &x,int l,int r,int fa)
{
    if(l>r)return;
    int m = (l+r)>>1;
    newnode(x,fa,a[m]);
    build(ch[x][0],l,m-1,x);
    build(ch[x][1],m+1,r,x);
    pushup(x);
}

void init()
{
    root = tot1 = tot2 = 0;
    pre[root] = ch[root][1] = ch[root][0] = addv[root] = key[root] = rev[root] = sz[root] = 0;
    minv[root] = INF;
    newnode(root,0,INF);
    newnode(ch[root][1],root,INF);
    build(keyv,1,n,ch[root][1]);
    pushup(ch[root][1]);
    pushup(root);

}

void rotate(int x,int d)
{
    int y = pre[x];
    pushdown(y);
    pushdown(x);
    ch[y][!d] = ch[x][d];
    pre[ch[x][d] ] = y;
    if(pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = x;
    pre[x] = pre[y];
    ch[x][d] = y;
    pre[y] = x;
    pushup(y);
}

void splay(int r,int goal)
{
    while(pre[r] != goal)
    {
        if(pre[pre[r]] == goal)
            rotate(r,ch[pre[r]][0]==r);
        else
        {
            int y = pre[r];
            int d = ch[pre[y]][0] == y;
            if(ch[y][d] == r)
            {
                rotate(r,!d);
                rotate(r,d);
            }
            else
            {
                rotate(y,d);
                rotate(r,d);
            }
        }
    }
    pushup(r);
    if(goal==0)root = r;
}

int kth(int r,int k)
{
    pushdown(r);
    int t = sz[ch[r][0]];
    if(t+1 == k) return r;
    else if(k<=t) return kth(ch[r][0],k);
    else return kth(ch[r][1],k-1-t);
}
int getmax(int r)
{
    pushdown(r);
    while(ch[r][1])
    {
        r = ch[r][1];
        pushdown(r);
    }
    return r;
}

int getmin(int r)
{
    pushdown(r);
    while(ch[r][0])
    {
        r = ch[r][0];
        pushdown(r);
    }
    return r;
}


/**本题*/
void add(int l,int r,int v)
{
    splay(kth(root,l),0);
    splay(kth(root,r+2),root);
    update_add(keyv,v);
    pushup(ch[root][1]);
    pushup(root);
}

void Reverse(int l,int r)
{
    splay(kth(root,l),0);
    splay(kth(root,r+2),root);
    update_rev(keyv);
    pushup(ch[root][1]);
    pushup(root);
}

void revolve(int l,int r,int T)///区间循环移位
{
    int len = r-l+1;
    T = (T%len);
    if(T==0)return;
    int m = r - T;/**区间[l,m],[m+1,r]调换位置*/
    splay(kth(root,m+1),0);
    splay(kth(root,r+2),root);
    int tmp = keyv;
    keyv = 0;
    pushup(ch[root][1]);
    pushup(root);///先把第二个区间删除。

    splay(kth(root,l),0);
    splay(kth(root,l+1),root);
    keyv = tmp;
    pre[tmp] = ch[root][1];
    pushup(ch[root][1]);
    pushup(root);///再插入第一个区间前。 这样做的前提是两个区间是相邻的！
}

void Insert(int x,int p)///插入
{
    splay(kth(root,x+1),0);///x后
    splay(kth(root,x+2),root);///x+1前
    newnode(keyv,ch[root][1],p);
    pushup(ch[root][1]);
    pushup(root);
}

void Erase(int r)
{
    if(r)
    {
        s[++tot2] = r;
        Erase(ch[r][0]);
        Erase(ch[r][1]);
    }
}

void ddelete(int r)///删除
{
    splay(kth(root,r),0);
    splay(kth(root,r+2),root);
    Erase(keyv);
    pre[keyv] = 0;
    keyv = 0;
    pushup(ch[root][1]);
    pushup(root);
}

int mmin(int l,int r)///区间最小
{
    splay(kth(root,l),0);
    splay(kth(root,r+2),root);
    return minv[keyv];
}
void Treavel(int x)
{
    if(x)
    {
        pushdown(x);
        Treavel(ch[x][0]);
        printf("%d   ",key[x]);
        Treavel(ch[x][1]);
    }
}
int main()
{
    int x,y,z;
    char op[20];
    while(scanf("%d",&n)==1)
    {
        for(int i=1;i<=n;i++)
            scanf("%d",a+i);
        init();
        scanf("%d",&q);
        while(q--)
        {
            scanf("%s",op);
            if(strcmp(op,"ADD") == 0)
            {
                scanf("%d%d%d",&x,&y,&z);
                add(x,y,z);
            }
            else if(strcmp(op,"REVERSE")==0)
            {
                scanf("%d%d",&x,&y);
                Reverse(x,y);
            }
            else if(strcmp(op,"REVOLVE")==0)
            {
                scanf("%d%d%d",&x,&y,&z);
                revolve(x,y,z);
            }
            else if(strcmp(op,"DELETE")==0)
            {
                scanf("%d",&x);
                ddelete(x);
            }
            else if(strcmp(op,"MIN")==0)
            {
                scanf("%d%d",&x,&y);
                printf("%d\n",mmin(x,y));
            }
            else if(strcmp(op,"INSERT")==0)
            {
                scanf("%d%d",&x,&y);
                Insert(x,y);
            }
            //Treavel(root);

        }
    }
}