SuperMemo
| Time Limit: 5000MS | Memory Limit: 65536K | |
| Total Submissions: 16499 | Accepted: 5203 | |
| 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
Source
POJ Founder Monthly Contest – 2008.04.13, Yao Jinyu题意：
add x,y D：第x个数到第y个数之间的数每个加D；
reverse x y：第x个数到第y个数之间全部数翻转；
revolve x y T：第x个数到第y个数之间的数，向后循环流动T次，即后面T个数变成这段子序列的最前面T个，前面的被挤到后面。
insert x P：在第x个数后面插入一个数P。
delete x：删除第x个数。
min x，y：求第x个数到第y个数之间的最小数字。
代码：
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL INF = 1e18;
const int maxn = 200005;
int a[maxn];
int ch[maxn][2], fa[maxn];
int sz[maxn], rev[maxn];
LL val[maxn], sum[maxn], add[maxn], Min[maxn];
int tol, rt;
void newNode(int p, int __val, int __fa){
val[p] = __val;
sum[p] = __val;
Min[p] = __val;
fa[p] = __fa;
sz[p] = 1;
rev[p] = add[p] = 0;
ch[p][0] = ch[p][1] = 0;
}
void mark_add(int p, LL __add){
add[p] += __add;
val[p] += __add;
sum[p] += __add * sz[p];
Min[p] += __add;
}
void mark_rev(int p){
rev[p] ^= 1;
swap(ch[p][0], ch[p][1]);
}
void push_down(int p){
if(rev[p]){
mark_rev(ch[p][0]);
mark_rev(ch[p][1]);
rev[p] = 0;
}
if(add[p]){
mark_add(ch[p][0], add[p]);
mark_add(ch[p][1], add[p]);
add[p] = 0;
}
}
void push_up(int p){
int ls = ch[p][0], rs = ch[p][1];
sz[p] = sz[ls] + sz[rs] + 1;
sum[p] = sum[ls] + sum[rs] + val[p];
Min[p] = min(val[p], min(Min[ls], Min[rs]));
}
void Rotate(int x, int t){
int p = fa[x];
push_down(p);
push_down(x);
fa[x] = fa[p];
if(fa[p])
ch[fa[p]][ch[fa[p]][1] == p] = x;
ch[p][!t] = ch[x][t];
if(ch[x][t])
fa[ch[x][t]] = p;
ch[x][t] = p;
fa[p] = x;
push_up(p);
}
void splay(int x, int y){
if(!x) return;
push_down(x);
while(fa[x] != y){
int p = fa[x];
if(fa[p] == y){
push_down(p);
push_down(x);
Rotate(x, ch[p][0] == x);
}else{
int g = fa[p];
push_down(g);
push_down(p);
push_down(x);
if(ch[g][0] == p){
if(ch[p][0] == x){
Rotate(p, 1);
Rotate(x, 1);
}else{
Rotate(x, 0);
Rotate(x, 1);
}
}else{
if(ch[p][1] == x){
Rotate(p, 0);
Rotate(x, 0);
}else{
Rotate(x, 1);
Rotate(x, 0);
}
}
}
}
push_up(x);
if(!y) rt = x;
}
int build(int l, int r, int fa){
if(l > r) return 0;
int mid = (l + r) >> 1;
newNode(mid, a[mid], fa);
ch[mid][0] = build(l, mid - 1, mid);
ch[mid][1] = build(mid + 1, r, mid);
push_up(mid);
return mid;
}
int get_pos(int k){
int p = rt;
while(1){
push_down(p);
if(sz[ch[p][0]] >= k)
p = ch[p][0];
else if(sz[ch[p][0]] + 1 == k)
break;
else{
k -= sz[ch[p][0]] + 1;
p = ch[p][1];
}
}
return p;
}
void Add(int a, int b, int c){
int pre = get_pos(a - 1);
int nxt = get_pos(b + 1);
splay(pre, 0);
splay(nxt, pre);
mark_add(ch[nxt][0], c);
push_up(nxt);
push_up(pre);
}
void Rev(int a, int b){
int pre = get_pos(a - 1);
int nxt = get_pos(b + 1);
splay(pre, 0);
splay(nxt, pre);
mark_rev(ch[nxt][0]);
push_up(nxt);
push_up(pre);
}
void Ins(int x, int P){
int nxt = get_pos(x + 1);
int now = get_pos(x);
splay(nxt, 0);
splay(now, nxt);
ch[now][1] = ++tol;
newNode(ch[now][1], P, now);
push_up(now);
push_up(nxt);
}
void Del(int x){
int pre = get_pos(x - 1);
int nxt = get_pos(x + 1);
splay(pre, 0);
splay(nxt, pre);
ch[nxt][0] = 0;
push_up(nxt);
push_up(pre);
}
void Revolve(int a, int b, int T){ //[a, c - 1], [c, b]
int l = b - a + 1;
int g = (T % l + l) % l + 1;
if(g == 1) return;//原样不动！
//删除[c, b]
int c = a + l - g + 1;
int pre = get_pos(c - 1);
int nxt = get_pos(b + 1);
splay(pre, 0);
splay(nxt, pre);
int p = ch[nxt][0];
ch[nxt][0] = 0;
push_up(nxt);
push_up(pre);
//将[c, b]插入a的前面
pre = get_pos(a - 1);
nxt = get_pos(a);
splay(pre, 0);
splay(nxt, pre);
ch[nxt][0] = p;
fa[p] = nxt;
push_up(nxt);
push_up(pre);
}
int get_min(int a, int b){
int pre = get_pos(a - 1);
int nxt = get_pos(b + 1);
splay(pre, 0);
splay(nxt, pre);
return Min[ch[nxt][0]];
}
void init(int n){
tol = 0;
ch[0][0] = ch[0][1] = fa[0] = sz[0] = rev[0] = 0;
val[0] = sum[0] = add[0] = 0;
Min[0] = INF;
newNode(rt = n + 1, 0, 0);
newNode(ch[rt][1] = n + 2, 0, rt);
ch[ch[rt][1]][0] = build(1, n, ch[rt][1]);
tol = n + 2;
}
int main(){
int n, m, x, y, D, P, T;
char opt[10];
while(scanf("%d", &n) != EOF){
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
}
init(n);
scanf("%d", &m);
while(m--){
scanf("%s", opt);
if(opt[0] == 'A'){
scanf("%d%d%d", &x, &y, &D); x++; y++;
Add(x, y, D);
}else if(opt[0] == 'R' && opt[3] == 'E'){
scanf("%d%d", &x, &y); x++; y++;
Rev(x, y);
}else if(opt[0] == 'R'){
scanf("%d%d%d", &x, &y, &T); x++; y++;
Revolve(x, y, T);
}else if(opt[0] == 'I'){
scanf("%d%d", &x, &P); x++;
Ins(x, P);
}else if(opt[0] == 'D'){
scanf("%d", &x); x++;
Del(x);
}else{
scanf("%d%d", &x, &y); x++; y++;
printf("%d\n", get_min(x, y));
}
}
}
return 0;
}更多推荐
POJ 3580 SuperMemo（Splay树）
发布评论