SuperMemo

     

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:

  1. 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}
  2. 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}
  3. 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}
  4. 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}
  5. DELETE x: delete Ax. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}
  6. 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

5
1 
2 
3 
4 
5
2
ADD 2 4 1
MIN 4 5

Sample Output

5

伸展树模版题
容易出错的点：

1.增量操作更新错误
2.数列滚动操作考虑左滚动情况
3.滚动操作子树放的位置以及pushup操作注意更新
4.若要更新的子树为终端结点则不必更新，否则会因为更新了出了负数而pushup出错
代码后附测试数据


#include<cstring>
#include<string>
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
#include<vector>
//#pragma comment(linker, "/STACK:1024000000,1024000000");

using namespace std;

#define INF 0x3f3f3f3f
#define keytree (ch[ch[root][1]][0])
#define maxn 200010

int pre[maxn],ch[maxn][2],siz[maxn],key[maxn];
int add[maxn];
int root,tot1;
int rev[maxn],mx[maxn];
int s[maxn],tot2;
int a[maxn];
int n,q;

/*
void travel(int x)
{
    if(x)
    {
        travel(ch[x][0]);
        printf("%d l:%d r:%d f:%d siz:%d key:%d mx:%d add:%d\n",x,ch[x][0],ch[x][1],pre[x],siz[x],key[x],mx[x],add[x]);
        travel(ch[x][1]);
    }
}

void debug()
{
    printf("root: %d\n",root);
    travel(root);
}
*/

inline void newnode(int &r,int f,int k)
{
    if(tot2) r=s[tot2--];
    else r=++tot1;
    pre[r]=f;
    ch[r][0]=ch[r][1]=0;
    key[r]=k;
    mx[r]=k;
    add[r]=0;
    rev[r]=0;
    siz[r]=1;
}

inline void update_rev(int r)
{
    if(!r) return ;
    swap(ch[r][0],ch[r][1]);
    rev[r]^=1;
}

inline void update_add(int r,int val)
{
    if(!r) return ;
    add[r]+=val;
    key[r]+=val;
    mx[r]+=val;
}

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

inline void pushup(int r)
{
    int lson=ch[r][0],rson=ch[r][1];
    siz[r]=siz[lson]+siz[rson]+1;
    mx[r]=key[r];
    mx[r]=min(mx[lson],mx[r]);
    mx[r]=min(mx[rson],mx[r]);
}

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

void init()
{
    root=tot1=tot2=0;
    ch[root][0]=ch[root][1]=siz[root]=pre[root]=0;
    rev[root]=0;
    key[root]=INF;
    mx[root]=INF;
    add[root]=0;
    newnode(root,0,INF);
    newnode(ch[root][1],root,INF);
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    build(keytree,0,n-1,ch[root][1]);
    pushup(ch[root][1]);
    pushup(root);
}

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

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

inline int get_kth(int r,int k)
{
    pushdown(r);
    int t=siz[ch[r][0]]+1;
    if(t==k) return r;
    if(t>k) return get_kth(ch[r][0],k);
    else return get_kth(ch[r][1],k-t);
}

inline void Insert(int pos,int tot)
{
    for(int i=0; i<tot; i++) scanf("%d",&a[i]);
    splay(get_kth(root,pos+1),0);
    splay(get_kth(root,pos+2),root);
    build(keytree,0,tot-1,ch[root][1]);
    pushup(ch[root][1]);
    pushup(root);
}

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

inline void Delete(int pos,int tot)
{
    splay(get_kth(root,pos),0);
    splay(get_kth(root,pos+tot+1),root);
    Erase(keytree);
    pre[keytree]=0;
    keytree=0;
    pushup(ch[root][1]);
    pushup(root);
}

inline void Reverse(int pos,int tot)
{
    splay(get_kth(root,pos),0);
    splay(get_kth(root,pos+tot+1),root);
    update_rev(keytree);
    pushup(ch[root][1]);
    pushup(root);
}

inline void Add(int l,int r,int num)
{
    splay(get_kth(root,l),0);
    splay(get_kth(root,r+2),root);
    key[keytree]+=num;
    add[keytree]+=num;
    mx[keytree]+=num;
}

void Revolve(int l,int r,int c)
{
    int mod=r-l+1;
    if(c<0)
    {
        c=-c;
        c%=mod;
        if(!c) return ;
        c=mod-c;
    }
    else c=c%mod;
    if(!c) return ;
    int mid=r-c+1;
    splay(get_kth(root,mid),0);
    splay(get_kth(root,r+2),root);
    int temp=keytree;
    keytree=0;
    pushup(ch[root][1]);
    pushup(root);
    splay(get_kth(root,l),0);
    splay(get_kth(root,l+1),root);
    keytree=temp;
    pre[temp]=ch[root][1];
    pushup(ch[root][1]);
    pushup(root);
}


int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
        scanf("%d",&q);
        while(q--)
        {
            char op[20];
            scanf("%s",op);
            if(!strcmp(op,"ADD"))
            {
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                if(a>b) swap(a,b);
                Add(a,b,c);
            }
            else if(!strcmp(op,"REVERSE"))
            {
                int a,b;
                scanf("%d%d",&a,&b);
                if(a>b) swap(a,b);
                Reverse(a,b-a+1);
            }
            else if(!strcmp(op,"REVOLVE"))
            {
                int a,b,c;
                scanf("%d%d%d",&a,&b,&c);
                Revolve(a,b,c);
            }
            else if(!strcmp(op,"INSERT"))
            {
                int a;
                scanf("%d",&a);
                Insert(a,1);
            }
            else if(!strcmp(op,"DELETE"))
            {
                int a;
                scanf("%d",&a);
                Delete(a,1);
            }
            else if(!strcmp(op,"MIN"))
            {
                int a,b;
                scanf("%d%d",&a,&b);
                splay(get_kth(root,a),0);
                splay(get_kth(root,b+2),root);
                printf("%d\n",mx[keytree]);
            }
        }
    }
    return 0;
}

/*
5
1 2 3 4 5
222
ADD 2 4 1
MIN 1 5
MIN 2 4
REVERSE 2 4
REVERSE 2 4
MIN 2 4
MIN 1 3
REVERSE  1 5
INSERT 2 4
MIN 2 4
DELETE 3
MIN 2 4
REVOLVE 2 5 7
REVERSE 1 5
MIN 1 5
MIN 2 4
MIN 2 3
*/



更多推荐

POJ 3580 OpenJ_Bailian 4090 SuperMemo (伸展树模版)