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裝置模型（中）之上層容器