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 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 (伸展树模版)
发布评论