题目描述

Description

给出一个初始序列fA1;A2;:::Ang，要求你编写程序支持如下操作： 1. ADDxyD：给子序列fAx:::Ayg的每个元素都加上D。例如对f1,2, 3,4,5g执行"ADD 241" 会得到f1,3,4,5,5g。 2. REVERSExy：将子序列fAx:::Ayg翻转。例如对f1,2,3,4,5g执 行"REVERSE 24"会得到f1,4,3,2,5g。 3. REVOLVExyT：将子序列fAx:::Ayg旋转T个单位。例如， 对f1,2,3,4,5g执行"REVOLVE 242"会得到f1,3,4,2,5g。 4. INSERTxP：在Ax后插入P。例如，对f1,2,3,4,5g执行"INSERT 24"会得到f1,2,4,3,4,5g。 5. DELETEx：删去Ax。例如，对f1,2,3,4,5g执行"DELETE 2"会得 到f1,3,4,5g。 6. MINxy：查询子序列fAx:::Ayg中的最小元素。例如，对于序列f1, 2,3,4,5g，询问"MIN 24"的返回应为2。

Input

第一行包含一个整数n，表示初始序列的长度。 以下n行每行包含一个整数，描述初始的序列。 接下来一行包含一个整数m，表示操作的数目。 以下m行每行描述一个操作。

Output

对于所有"MIN"操作，输出正确的答案，每行一个。

Sample Input

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

Sample Output

5

HINT

输入、输出以及中间运算结果均不会超过32位整数。
对于30%的数据，n;m 6 1000;
对于100%的数据，n;m 6 100000。

题目分析

非旋转treap 裸题

#include <cstdio>
#include <cstring>
#include <cmath>
#include <ctime>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int,int> par;
int n,m;
int val[101000*3],size[101000*3],key[101000*3],lson[101000*3],rson[101000*3];
int add[101000*3],lazy[101000*3],minn[101000*3];    
int tot,root;
void update(int x)
{
    size[x]=size[lson[x]]+size[rson[x]]+1;
    minn[x]=val[x];
    if(lson[x]) minn[x]=min(minn[x],minn[lson[x]]);
    if(rson[x]) minn[x]=min(minn[x],minn[rson[x]]);
}
void pushdown(int x)
{
    if(add[x])
    {
        add[lson[x]]+=add[x],add[rson[x]]+=add[x];
        val[lson[x]]+=add[x],val[rson[x]]+=add[x];
        minn[lson[x]]+=add[x],minn[rson[x]]+=add[x];
        add[x]=0;
    }
    if(lazy[x])
    {
        swap(lson[x],rson[x]);
        lazy[lson[x]]^=1,lazy[rson[x]]^=1;
        lazy[x]=0;
    }
}
int merge(int x,int y)
{
    if(x==0||y==0) return x|y;
    pushdown(x),pushdown(y);
    if(key[x]<key[y])
    {
        lson[y]=merge(x,lson[y]),update(y);
        return y;
    }
    rson[x]=merge(rson[x],y),update(x);
    return x;
}
par split(int x,int k)
{
    if(k==0) return make_pair(0,x);
    pushdown(x);
    int l=lson[x],r=rson[x];
    if(k==size[lson[x]])
    {
        lson[x]=0,update(x);
        return make_pair(l,x);
    }
    if(k==size[lson[x]]+1)
    {
        rson[x]=0,update(x);
        return make_pair(x,r);
    }
    par t;
    if(k<size[lson[x]])
    {
        t=split(l,k);
        lson[x]=t.second,update(x);
        return make_pair(t.first,x);
    }
    else
    {
        t=split(r,k-size[lson[x]]-1);
        rson[x]=t.first,update(x);
        return make_pair(x,t.second);
    }
}
char s[10];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&val[i]),size[++tot]=1,minn[tot]=val[i],key[tot]=rand()*rand(),root=merge(root,tot);
    scanf("%d",&m);
    for(int i=1;i<=m;i++) 
    {
        int x,y,c;
        scanf("%s",&s[0]);
        if(s[0]=='A')
        {
            scanf("%d%d%d",&x,&y,&c);
            if(x>y) swap(x,y);
            par t1,t2;
            t2=split(root,y);
            t1=split(t2.first,x-1);
            add[t1.second]+=c,val[t1.second]+=c,minn[t1.second]+=c;
            root=merge(merge(t1.first,t1.second),t2.second);
        }
        else if(s[0]=='I')
        {
            scanf("%d%d",&x,&y);
            par t1=split(root,x);
            size[++tot]=1,val[tot]=y,key[tot]=rand()*rand(),minn[tot]=y;
            root=merge(merge(t1.first,tot),t1.second);
        }
        else if(s[0]=='D')
        {
            scanf("%d",&x);
            par t1,t2;
            t2=split(root,x);
            t1=split(t2.first,x-1);
            root=merge(t1.first,t2.second);
        }
        else if(s[0]=='M')
        {
            scanf("%d%d",&x,&y);
            if(x>y) swap(x,y);
            par t1,t2;
            t2=split(root,y);
            t1=split(t2.first,x-1);
            printf("%d\n",minn[t1.second]);
            root=merge(merge(t1.first,t1.second),t2.second);
        }
        else if(s[3]=='E')
        {
            scanf("%d%d",&x,&y);
            if(x>y) swap(x,y);
            par t1,t2;
            t2=split(root,y);
            t1=split(t2.first,x-1);
            lazy[t1.second]^=1;
            root=merge(merge(t1.first,t1.second),t2.second);
        }
        else
        {
            scanf("%d%d%d",&x,&y,&c);
            c%=(y-x+1);
            par t2=split(root,y);
            par t1=split(t2.first,x-1);
            par t3=split(t1.second,y-x+1-c);
            root=merge(merge(t1.first,merge(t3.second,t3.first)),t2.second);
        }
    }
}