POJ3580 SuperMemo SPLAY 各种操作。。。。

这道题目需要实现SPLAY的各种操作。。。。。码了大半天，幸亏1A，否则今晚是不用睡觉了。。。。。

一共六个操作

1：删除第K个节点

2：在第k个节点后面插入一个数

3：将区间[l,r]翻转

4：将区间[l,r]每个节点加上一个数

5：查询区间[l,r]的最小值

以上五种操作都很基本，只不过维护两个lazy标记而已，push_down的时候多做一步而已，关键是下面那个操作。

6：在区间[l,r]上做循环左移t次的操作，本质合并两个相邻的区间[a,b][b+1,c];这里两个区间的分界我们可以用t对（b-a+1）取模得到z然后右边的区间是【y-z+1，y】，具体的区间交换方法是将a-1旋转的ROOT ，然后将b旋转到ROOT的右儿子，然后将c旋转到ROOT的右儿子的右儿子。这里有特殊之处，以往我们需要操作的区间位于一个儿子节点的左子树。而这次我们要操作的区间是一个儿子节点和他的左子树。也就是说b连同他的左子树是我们要查找的[a,b]区间，c连同他的左子树是我们要查找的区间[b+1,c]然后做树进行操作就行了，这里要注意改变位置前要push_down，改变位置后要push_up 这两个操作不要啦。。。宁愿多写也不要少写。。。。

注意点：revovle操作里面的t可能为负。另外当求出的位移值为0是不需要操作此处要特判。

SuperMemo

Time Limit: 5000MS	Memory Limit: 65536K
Total Submissions: 5850	Accepted: 1889
Case Time Limit: 2000MS

Description

Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, {A1,A2, ... An}. Then the host performs a series of operations and queries on the sequence which consists:

ADD x y D: Add D to each number in sub-sequence {Ax ...Ay}. For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}
REVERSE x y: reverse the sub-sequence {Ax ...Ay}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
REVOLVE x y T: rotate sub-sequence {Ax ...Ay} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
INSERT x P: insert P after Ax. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
DELETE x: delete Ax. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
MIN x y: query the participant what is the minimum number in sub-sequence {Ax ...Ay}. For example, the correct answer to "MIN 2 4" on {1, 2, 3, 4, 5} is 2

To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

Input

The first line contains n (n ≤ 100000).

The following n lines describe the sequence.

Then follows M (M ≤ 100000), the numbers of operations and queries.

The following M lines describe the operations and queries.

Output

For each "MIN" query, output the correct answer.

Sample Input

Sample Output

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<cstdio>

using namespace std;

#define MAXN 200000
#define INF 0x3ffffff

int a[MAXN],m,n;
int next[MAXN];
struct nodes
{
    int ch[2],f;
    int key,size,w,col,ad,mi;
}node[MAXN];

void init()
{
    for(int i=0;i<MAXN-10;i++)
        next[i]=i+1;
}

int newnode(int key)
{
    int p=next[0];
    next[0]=next[p];
    node[p].key=key;
    node[p].w=node[p].size=1;
    node[p].mi=key;
    node[p].ad=node[p].col=0;
    node[p].ch[0]=node[p].ch[1]=node[p].f=0;
    return p;
}

void delnode(int p)
{
    next[p]=next[0];
    next[0]=p;
}

struct spt
{
    int root;
    void clear()
    {
        root=0;
    }
    void rotate(int x,int c)
    {
        int y=node[x].f;
        push_down(y);push_down(x);
        node[y].ch[!c]=node[x].ch[c];
        if(node[x].ch[c])
                node[node[x].ch[c]].f=y;
        node[x].f=node[y].f;
        if(node[y].f)
        {
            if(node[node[y].f].ch[0]==y)
                node[node[y].f].ch[0]=x;
            else
                node[node[y].f].ch[1]=x;
        }
        node[x].ch[c]=y;
        node[y].f=x;
        push_up(y);
        if(y==root) root=x;
    }
    void splay(int x,int f)
    {
        push_down(x);
        for(;node[x].f!=f;)
        {
            push_down(node[node[x].f].f);
            push_down(node[x].f);
            push_down(x);
            if(node[node[x].f].f==f)
            {
                if(node[node[x].f].ch[0]==x)
                    rotate(x,1);
                else
                    rotate(x,0);
            }
            else
            {
                int y=node[x].f;
                int z=node[y].f;
                if(node[z].ch[0]==y)
                {
                    if(node[y].ch[0]==x)
                        rotate(y,1),rotate(x,1);
                    else
                        rotate(x,0),rotate(x,1);
                }
                else
                {
                    if(node[y].ch[1]==x)
                        rotate(y,0),rotate(x,0);
                    else
                        rotate(x,1),rotate(x,0);
                }
            }
        }
        push_up(x);
        if(!f) root=x;
    }
    void remove()
    {
        int t=root;
        if(node[t].ch[1])
        {
            root=node[root].ch[1];
            select(1,0);
            node[root].ch[0]=node[t].ch[0];
            if(node[t].ch[0]) node[node[t].ch[0]].f=root;
        }
        else root=node[root].ch[0];
        node[root].f=0;
        push_up(root);
        delnode(t);
    }
    void revolve(int a,int b,int c)
    {
        int pa,pb,pc,px;
        pa=select(a,0);
        pb=select(b+1,pa);
        pc=select(c+1,pb);
        px=node[pc].ch[1];
        push_down(pa);
        push_down(pb);
        push_down(pc);
        node[pa].ch[1]=pc,node[pc].f=pa;
        node[pb].ch[1]=px,node[px].f=pb;
        node[pc].ch[1]=pb,node[pb].f=pc;
        push_up(pb);
        push_up(pc);
        push_up(pa);
    }
    void reverse(int l,int r)
    {
        select(l,0);
        select(r+2,root);
        node[node[node[root].ch[1]].ch[0]].col^=1;
    }
    void insert(int x,int a)
    {
        int p=newnode(a);
        select(x+1,0);
        x=getmin(node[root].ch[1]);
        splay(x,root);
        node[node[root].ch[1]].ch[0]=p;
        node[p].f=x;
        push_up(p);
        push_up(node[root].ch[1]);
        push_up(root);
    }
    int minA2B(int a,int b)
    {
        select(a,0);
        select(b+2,root);
        push_up(node[root].ch[1]);
        push_up(root);
        return node[node[node[root].ch[1]].ch[0]].mi;
    }
    int select(int k,int rt)
    {
        int tmp,t=root;
        for(;;)
        {
            push_down(t);
            int l=node[node[t].ch[0]].size;
            if(k>l && k<=l+node[t].w) break;
            if(k<=l)
                t=node[t].ch[0];
            else
                k-=(l+node[t].w),t=node[t].ch[1];
        }
        splay(t,rt);
        return t;
    }
    int getmin(int p)
    {
        push_down(p);
        while(node[p].ch[0])
        {
            p=node[p].ch[0];
            push_down(p);
        }
        return p;
    }
    void add(int l,int r,int a)
    {
        select(l,0);
        select(r+2,root);
        node[node[node[root].ch[1]].ch[0]].key+=a;
        node[node[node[root].ch[1]].ch[0]].ad+=a;
        node[node[node[root].ch[1]].ch[0]].mi+=a;
    }
    void push_down(int rt)
    {
        if(rt && node[rt].col)
        {
            swap(node[rt].ch[0],node[rt].ch[1]);
            int l=node[rt].ch[0];
            int r=node[rt].ch[1];
            node[l].col^=1;
            node[r].col^=1;
            node[rt].col=0;
        }
        if(rt && node[rt].ad)
        {
            int l=node[rt].ch[0];
            int r=node[rt].ch[1];
            node[l].key+=node[rt].ad;
            node[r].key+=node[rt].ad;
            node[l].ad+=node[rt].ad;
            node[r].ad+=node[rt].ad;
            node[l].mi+=node[rt].ad;
            node[r].mi+=node[rt].ad;
            node[rt].ad=0;
        }
    }
    void push_up(int rt)
    {
        if(!rt)return;
        int l=node[rt].ch[0];
        int r=node[rt].ch[1];
        int ll=INF,rr=INF;
        int ret=node[rt].w;
        if(l) ret+=node[l].size,ll=node[l].mi;
        if(r) ret+=node[r].size,rr=node[r].mi;
        node[rt].size=ret;
        node[rt].mi=min(node[rt].key,min(ll,rr));
    }
    void del(int p)
    {
        if(!p) return;
        del(node[p].ch[0]);
        del(node[p].ch[1]);
        delnode(p);
    }
    int build(int l,int r,int f)
    {
        if(l>r) return 0;
        int m=(l+r)>>1;
        int p=newnode(a[m]);
        node[p].f=f;
        node[p].ch[0]=build(l,m-1,p);
        node[p].ch[1]=build(m+1,r,p);
        push_up(p);
        return p;
    }
};
spt s1;
void prepare()
{
    s1.clear();
    s1.root=newnode(INF);
    node[s1.root].ch[1]=newnode(INF);
    node[node[s1.root].ch[1]].f=s1.root;
    node[node[s1.root].ch[1]].ch[0]=s1.build(1,n,node[s1.root].ch[1]);
    s1.push_up(node[s1.root].ch[1]);
    s1.push_up(s1.root);
}

int main()
{
    char q[10];
    int x,y,z;
    init();
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        prepare();
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%s",q);
            if(strcmp(q,"ADD")==0)
            {
                scanf("%d%d%d",&x,&y,&z);
                s1.add(x,y,z);
            }
            if(strcmp(q,"REVERSE")==0)
            {
                scanf("%d%d",&x,&y);
                s1.reverse(x,y);
            }
            if(strcmp(q,"INSERT")==0)
            {
                scanf("%d%d",&x,&y);
                s1.insert(x,y);
            }
            if(strcmp(q,"DELETE")==0)
            {
                scanf("%d",&x);
                s1.select(x+1,0);
                s1.remove();
            }
            if(strcmp(q,"MIN")==0)
            {
                scanf("%d%d",&x,&y);
                printf("%d\n",s1.minA2B(x,y));
            }
            if(strcmp(q,"REVOLVE")==0)
            {
                scanf("%d%d%d",&x,&y,&z);
                z=(z%(y-x+1)+(y-x+1))%(y-x+1);
                if(z==0) continue;
                s1.revolve(x,y-z,y);
            }
        }
        s1.del(s1.root);
    }
    return 0;
}

POJ3580 SuperMemo SPLAY 各种操作。。。。

继续阅读

树的基本概念(定义、基本术语、性质)

GSL--GNU Scientific Library

D5|哈希表，善用数据结构

如何成为一名.net 工程师?

BMP文件结构及图像每行字节计算方法

D. Ehab the Xorcist(构造+思维)

查找算法之二分查找查找算法之二分查找

JAVA高效编程指南

CQ V1.0分词bates(基于双数组tire树)—应该是目前最快的中文分词算法

【数据结构】医院选址

[转]ISUP信令的IAM消息详细内容

笔试面试题目：滑动窗口(二)

交通/城市相关的公开的数据集上学时整理的Xie et al., 2020收集的

数据结构与算法（27）——排序（二）

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

Linux设备模型（中）之上层容器