SuperMemo
| Time Limit: 5000MS | Memory Limit: 65536K |
| Total Submissions: 11106 | Accepted: 3494 |
| Case Time Limit: 2000MS |
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 题意：给定一个区间，有如下几种操作，增加值，翻转，平移，在第x位置后面插入值，删除第x个值，查询区间最小值。
不难发现这些操作都是splay树的经典区间操作，照着模板来一发即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
#define rep(i,a,b) for (int i=a;i<((b)+1);i++)
#define Rep(i,a,b) for (int i=a;i>=b;i--)
#define foreach(e,x) for (__typeof(x.begin()) e=x.begin();e!=x.end();e++)
#define mid ((l+r)>>1) //segement tree
#define lson (k<<1) //segement tree
#define rson (k<<1|1) //segement tree
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0] //splay tree
#define R ch[r][1] //splay tree
#define keyvalue ch[ch[root][1]][0] //splay tree
using namespace std;
const int N=1000050;
const long long Mod=1000000007;
const int inf=0x3f3f3f3f;
typedef pair<int, int> pii;
typedef long long ll;
int pre[N],ch[N][2],key[N],root,tot,_size[N],col[N],a[N],n,q,_tot,s[N];
int rev[N],m[N];
void newnode(int &r,int fa,int k) {
if (_tot) r=s[_tot--];
else r=++tot;
pre[r]=fa;_size[r]=1;key[r]=m[r]=k;
col[r]=rev[r]=0;
}
void update_rev(int r) {
if (r==0) return ;
swap(L,R);
rev[r]^=1;
}
void update_add(int r,int add) {
if (r==0) return ;
col[r]+=add;key[r]+=add;
m[r]+=add;
}
void push_up(int r) {
_size[r]=_size[L]+_size[R]+1;
m[r]=key[r];
m[r]=min(m[r],m[L]);
m[r]=min(m[r],m[R]);
}
void push_down(int r) {
if (rev[r]) {
update_rev(L);
update_rev(R);
rev[r]=0;
}
if (col[r]) {
update_add(L,col[r]);
update_add(R,col[r]);
col[r]=0;
}
}
void build(int &x,int l,int r,int fa) {
if (l>r) return ;
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=tot=_tot=0;
ch[root][0]=ch[root][1]=pre[root]=_size[root]=col[root]=rev[root]=0;
m[root]=inf;
newnode(root,0,inf);
newnode(ch[root][1],root,inf);
build(keyvalue,1,n,ch[root][1]);
push_up(ch[root][1]);
push_up(root);
}
void Rotate(int r,int k) {
int y=pre[r];
push_down(y);
push_down(r);
ch[y][!k]=ch[r][k];
pre[ch[r][k]]=y;
if (pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=r;
pre[r]=pre[y];
ch[r][k]=y;
pre[y]=r;
push_up(y);
}
void Splay(int r,int g) {
push_down(r);
while (pre[r]!=g) {
if (pre[pre[r]]==g) {
push_down(pre[r]);
push_down(r);
Rotate(r,ch[pre[r]][0]==r);
}else {
push_down(pre[pre[r]]);
push_down(pre[r]);
push_down(r);
int y=pre[r];
int k=ch[pre[y]][0]==y;
if (ch[y][k]==r) {
Rotate(r,!k);
Rotate(r,k);
}else {
Rotate(y,k);
Rotate(r,k);
}
}
}
push_up(r);
if (g==0) root=r;
}
int getkth(int r,int k) {
push_down(r);
int t=_size[L]+1;
if (t==k) return r;
if (t>k) return getkth(L, k);
else return getkth(R, k-t);
}
int getmin(int r) {
push_down(r);
while (L) {
r=L;
push_down(r);
}
return r;
}
int getmax(int r) {
push_down(r);
while (R) {
r=R;
push_down(r);
}
return r;
}
void Add(int l,int r,int x) {
Splay(getkth(root, l),0);
Splay(getkth(root, r+2),root);
update_add(keyvalue, x);
push_up(ch[root][1]);
push_up(root);
}
void Reverse(int l,int r) {
Splay(getkth(root, l),0);
Splay(getkth(root, r+2),root);
update_rev(keyvalue);
push_up(ch[root][1]);
push_up(root);
}
int query(int l,int r) {
Splay(getkth(root, l), 0);
Splay(getkth(root, r+2), root);
return m[keyvalue];
}
void erase(int r) {
if (r) {
s[++_tot]=r;
erase(L);erase(R);
}
}
void Insert(int p,int x) {
Splay(getkth(root, p+1), 0);
Splay(getkth(root, p+2), root);
newnode(keyvalue, ch[root][1], x);
push_up(ch[root][1]);
push_up(root);
}
void Delete(int x) {
Splay(getkth(root, x), 0);
Splay(getkth(root, x+2), root);
erase(keyvalue);
pre[keyvalue]=0;
keyvalue=0;
push_up(ch[root][1]);
push_up(root);
}
void Revolve(int l,int r,int t) {
int len=r-l+1;
t=(t%len+len)%len;
if (t==0) return ;
int c=r-t+1;
Splay(getkth(root, c),0);
Splay(getkth(root, r+2), root);
int tmp=keyvalue;
keyvalue=0;
push_up(ch[root][1]);
push_up(root);
Splay(getkth(root, l), 0);
Splay(getkth(root, l+1), root);
keyvalue=tmp;
pre[keyvalue]=ch[root][1];
push_up(ch[root][1]);
push_up(root);
}
char ss[20];
int main(int argc, const char * argv[]) {
while (~scanf("%d",&n)) {
rep(i,1,n) scanf("%d",&a[i]);
init();
scanf("%d",&q);
int x,y,z;
rep(i,1,q) {
scanf("%s",ss);
if (strcmp(ss, "ADD")==0) {
scanf("%d%d%d",&x,&y,&z);
Add(x, y, z);
}else if (strcmp(ss, "REVERSE")==0) {
scanf("%d%d",&x,&y);
Reverse(x, y);
}else if (strcmp(ss, "REVOLVE")==0) {
scanf("%d%d%d",&x,&y,&z);
Revolve(x, y, z);
}else if (strcmp(ss, "INSERT")==0) {
scanf("%d%d",&x,&y);
Insert(x, y);
}else if (strcmp(ss, "DELETE")==0) {
scanf("%d",&x);
Delete(x);
}else {
scanf("%d%d",&x,&y);
printf("%d\n",query(x, y));
}
}
}
return 0;
}
![D. Ehab the Xorcist(构造+思维)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)