裸Splay区间操作: 内存池+区间加减+区间翻转+插入+删除+维护最值
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: 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 2To 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 Source POJ Founder Monthly Contest 2008.04.13, Yao Jinyu |
|||||||||
[Submit] [Go Back] [Status] [Discuss]
#include#include #include #include using namespace std; const int maxn=220000; const int INF=0x3f3f3f3f; #define Key_Value ch[ch[root][1]][0] int ch[maxn][2],rev[maxn],add[maxn],sz[maxn],pre[maxn],key[maxn],minn[maxn]; int root,tot1; int s[maxn],tot2; int n,q,a[maxn]; void NewNode(int& x,int father,int k) { if(tot2) x=s[tot2--]; else x=++tot1; ch[x][0]=ch[x][1]=rev[x]=add[x]=0; sz[x]=1; pre[x]=father; key[x]=minn[x]=k; } void Erase(int r) { if(r) { s[++tot2]=r; Erase(ch[r][0]); Erase(ch[r][1]); } } void Upd_Rev(int x) { if(!x) return ; swap(ch[x][0],ch[x][1]); rev[x]^=1; } void Upd_Add(int x,int d) { if(!x) return ; key[x]+=d; minn[x]+=d; add[x]+=d; } void Push_Up(int x) { sz[x]=sz[ch[x][1]]+sz[ch[x][0]]+1; minn[x]=key[x]; if(ch[x][0]) minn[x]=min(minn[x],minn[ch[x][0]]); if(ch[x][1]) minn[x]=min(minn[x],minn[ch[x][1]]); } void Push_Down(int x) { if(rev[x]) { Upd_Rev(ch[x][0]); Upd_Rev(ch[x][1]); rev[x]=0; } if(add[x]) { Upd_Add(ch[x][0],add[x]); Upd_Add(ch[x][1],add[x]); add[x]=0; } } void Build(int& x,int l,int r,int fa) { if(l>r) return ; int mid=(l+r)/2; NewNode(x,fa,a[mid]); Build(ch[x][0],l,mid-1,x); Build(ch[x][1],mid+1,r,x); Push_Up(x); } void Init() { root=tot1=tot2=0; ch[root][0]=ch[root][1]=pre[root]=sz[root]=0; minn[root]=key[root]=INF; NewNode(root,0,INF); NewNode(ch[root][1],root,INF); Build(Key_Value,1,n,ch[root][1]); Push_Up(ch[root][1]); Push_Up(root); } void Rotate(int x,int kind) { int y=pre[x]; Push_Down(y); Push_Down(x); ch[y