POJ 3580 SuperMemo

POJ 3580 SuperMemo

題目概述:

一開始給一個長度為n的序列。

一共有6種操作。

1. ADD x y D: 把x到y位置的數都加D。

For example, performing "ADD 2 4 1" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5, 5}

2. REVERSE x y: 把x到y位置的數反轉。

For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}

3. REVOLVE x y T:把x到y的數平移T。

For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}

4. INSERT x P: 插入一個P在位置x後面。

For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}

5. DELETE x: 把第x位置刪除。

For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 5}

6. MIN x y:詢問x到y的最小值並輸出。

For example, the correct answer to "MIN 2 4" on {1, 2, 3, 4, 5} is 2

思路:

經典的treap題。

//By SCJ

#include<iostream>

#include<string>

#include<algorithm>

using namespace std;

//#define endl '\n'

#define int long long

#define INF 1000000000000000

struct treap;

treap *nul;

struct treap{

int val,sz,MIN,add;

bool rev;

treap *l,*r;

treap(int _val)

{

val=MIN=_val;

sz=1;

rev=add=0;

l=r=nul;

}

void down()

{

if(rev) swap(l,r);

l->rev^=rev;

r->rev^=rev;

l->add+=add;

r->add+=add;

val+=add;

add=rev=0;

}

void up()

{

sz=l->sz + r->sz + 1;

MIN=min(min(l->MIN+l->add,r->MIN+r->add),val+add);

}

};

treap *merge(treap *a,treap *b)

{

if(a==nul) return b;

if(b==nul) return a;

if(rand()%(a->sz + b->sz)<a->sz)

{

a->down();

a->r=merge(a->r,b);

a->up();

return a;

}

else{

b->down();

b->l=merge(a,b->l);

b->up();

return b;

}

}

void split(treap *t,treap *&a,treap *&b,int k)

{

if(t==nul) {a=b=nul;return;}

t->down();

if( (t->l->sz+1) <= k ){

a=t;

//a->down();

split(t->r,a->r,b,k- (t->l->sz+1) );

a->up();

}

else {

b=t;

//b->down();

split(t->l,a,b->l,k);

b->up();

}

}

signed main()

{

//ios::sync_with_stdio(0);

//cin.tie(0);

srand(1234);

nul=new treap(INF);nul->sz=0;

treap *root=nul;

int n;scanf("%lld",&n);

// cin>>n;

for(int i=1;i<=n;++i)

{

int x;scanf("%lld",&x);

// cin>>x;

treap *t=new treap(x);

root=merge(root,t);

}

int q;cin>>q;

while(q--)

{

int x,y,z;

treap *tl=nul,*tr=nul,*tp=nul;

string s;

cin>>s;

if(s[0]=='A')

{

scanf("%lld%lld%lld",&x,&y,&z);

// cin>>x>>y>>z;

split(root,tl,root,x-1);

split(root,root,tr,y-x+1);

root->add+=z;

root=merge(merge(tl,root),tr);

}

else if(s[0]=='R')

{

if(s[3]=='E')

{

scanf("%lld%lld",&x,&y);

// cin>>x>>y;

split(root,tl,root,x-1);

split(root,root,tr,y-x+1);

root->rev^=1;

root=merge(merge(tl,root),tr);

}

else

{

scanf("%lld%lld%lld",&x,&y,&z);

//cin>>x>>y>>z;

z%=(y-x+1);z=(y-x+1)-z;

split(root,tl,root,x-1);

split(root,root,tr,y-x+1);

split(root,tp,root,z);

root=merge(merge(merge(tl,root),tp),tr);

}

}

else if(s[0]=='I')

{

scanf("%lld%lld",&x,&y);

//cin>>x>>y;

split(root,tl,root,x);

tp=new treap(y);

root=merge(merge(tl,tp),root);

}

else if(s[0]=='D')

{

scanf("%lld",&x);

// cin>>x;

split(root,tl,root,x-1);

split(root,tp,root,1);

root=merge(tl,root);

}

else

{

scanf("%lld%lld",&x,&y);

// cin>>x>>y;

split(root,tl,root,x-1);

split(root,root,tr,y-x+1);

printf("%lld\n",root->MIN);

// cout<<root->MIN<<endl;

root=merge(merge(tl,root),tr);

}

}

}