Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 16260 | Accepted: 5111 | |
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
题意: 给定一个数列:a1,a2,.... an
进行以下6种操作:
①ADD x y D : 给第x个数到第y个数加D
②REVERSE x y : 反转[x,y]
③REVOVLE x y T : 对[x,y]区间的数循环右移T次
④INSERT x P : 在第x个数后面插入P
⑤DELETE x : 删除第x个数
⑥MIN x y : 查询[x,y]之间的最小的数
题解:Splay-Tree
进行REVOLVE操作的时候,先将T对(y-x+1)取模,然后该操作就相当于将[x+T-1,y]插入到[x,x+T]前面
#include<cstdio>
#include<string.h>
#include<algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MX = 2e5 + 5;
int n, m;
int a[MX];
int root, rear; //根节点,节点总数
int rem[MX], tot; //经过删除后未被使用的节点
int ch[MX][2], fa[MX];
int col[MX], val[MX], add[MX], Min[MX];
int sz[MX];
void NewNode(int &rt, int father, int v) {
if (tot) rt = rem[tot--];
else rt = ++rear;
fa[rt] = father;
ch[rt][0] = ch[rt][1] = col[rt] = add[rt] = 0;
Min[rt] = val[rt] = v;
sz[rt] = 1;
}
void PushUP(int rt) {
int ls = ch[rt][0], rs = ch[rt][1];
sz[rt] = sz[ls] + sz[rs] + 1;
Min[rt] = val[rt];
if (ls) Min[rt] = min(Min[rt], Min[ls]);
if (rs) Min[rt] = min(Min[rt], Min[rs]);
}
void up_val(int rt, int v) {
add[rt] += v;
Min[rt] += v;
val[rt] += v;
}
void up_rev(int rt) {
col[rt] ^= 1;
swap(ch[rt][0], ch[rt][1]);
}
void PushDown(int rt) {
int ls = ch[rt][0], rs = ch[rt][1];
if (col[rt]) {
if (ls) up_rev(ls);
if (rs) up_rev(rs);
col[rt] = 0;
}
if (add[rt]) {
if (ls) up_val(ls, add[rt]);
if (rs) up_val(rs, add[rt]);
add[rt] = 0;
}
}
void build(int &rt, int l, int r, int father) {
if (l > r) return;
int m = (l + r) >> 1;
NewNode(rt, father, a[m]);
build(ch[rt][0], l, m - 1, rt);
build(ch[rt][1], m + 1, r, rt);
PushUP(rt);
}
void init() {
root = rear = tot = 0;
Min[0] = INF;
NewNode(root, 0, INF); //一共n+2个节点,0~n+1
NewNode(ch[root][1], root, INF);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
build(ch[ch[root][1]][0], 1, n, ch[root][1]);
PushUP(root);
}
void Link(int x, int y, int c) {
fa[x] = y; ch[y][c] = x;
}
void Rotate(int x, int c) { //c=0表示左旋,c=1表示右旋
int y = fa[x];
PushDown(y);
PushDown(x);
Link(x, fa[y], ch[fa[y]][1] == y);
Link(ch[x][c], y, !c);
Link(y, x, c);
PushUP(y); //y变成x子节点,只要更新y
}
void Splay(int x, int f) {
PushDown(x);
while (fa[x] != f) {
int y = fa[x];
if (fa[y] == f) Rotate(x, ch[y][0] == x);
else {
int t = ch[fa[y]][0] == y;
if (ch[y][t] == x) Rotate(x, !t);
else Rotate(y, t);
Rotate(x, t);
}
}
PushUP(x); //更新x
if (f == 0) root = x;
}
int get_kth(int rt, int k) {
PushDown(rt);
int t = sz[ch[rt][0]] + 1, ret;
if (t == k) ret = rt;
else if (t > k) ret = get_kth(ch[rt][0], k);
else ret = get_kth(ch[rt][1], k - t);
PushUP(rt);
return ret;
}
//各种操作
void Update(int L, int R, int v) {
Splay(get_kth(root, L), 0);
Splay(get_kth(root, R + 2), root);
up_val(ch[ch[root][1]][0], v);
PushUP(ch[root][1]);
PushUP(root);
}
void Reverse(int L, int R) {
Splay(get_kth(root, L), 0);
Splay(get_kth(root, R + 2), root);
up_rev(ch[ch[root][1]][0]);
}
void Insert(int p, int v) {
Splay(get_kth(root, p + 1), 0); //将第p个数旋转到根节点
Splay(get_kth(root, p + 2), root); //将第p+1个数旋转到根节点的右儿子
NewNode(ch[ch[root][1]][0], ch[root][1], v);
PushUP(ch[root][1]);
PushUP(root);
n++;
}
void erase(int rt) {
if (!rt)return;
fa[rt] = 0;
rem[++tot] = rt;
n--;
erase(ch[rt][0]);
erase(ch[rt][1]);
}
void Delete(int p) {
Splay(get_kth(root, p), 0); //将第p-1个数旋转到根节点
Splay(get_kth(root, p + 2), root); //将第p+1个数旋转到根节点的右儿子
erase(ch[ch[root][1]][0]);
ch[ch[root][1]][0] = 0;
PushUP(ch[root][1]);
PushUP(root);
}
int Query(int L, int R) {
Splay(get_kth(root, L), 0);
Splay(get_kth(root, R + 2), root);
return Min[ch[ch[root][1]][0]];
}
void Revolve(int L, int R, int t) {
t %= (R - L + 1);
Splay(get_kth(root, R - t + 1), 0);
Splay(get_kth(root, R + 2), root);
int rc = ch[root][1];
t = ch[rc][0];
ch[rc][0] = 0;
PushUP(rc);
PushUP(root);
Splay(get_kth(root, L), 0);
Splay(get_kth(root, L + 1), root);
rc = ch[root][1];
ch[rc][0] = t;
fa[t] = rc;
PushUP(rc);
PushUP(root);
}
int main() {
char op[10];
int x, y, t;
//freopen("in.txt", "r", stdin);
while (~scanf("%d", &n)) {
init();
scanf("%d", &m);
while (m--) {
scanf("%s", op);
if (op[0] == 'A') {
scanf("%d%d%d", &x, &y, &t);
Update(x, y, t);
} else if (op[0] == 'R' && op[3] == 'E') {
scanf("%d%d", &x, &y);
Reverse(x, y);
} else if (op[0] == 'R' && op[3] == 'O') {
scanf("%d%d%d", &x, &y, &t);
Revolve(x, y, t);
} else if (op[0] == 'I') {
scanf("%d%d", &x, &t);
Insert(x, t);
} else if (op[0] == 'D') {
scanf("%d", &x);
Delete(x);
} else {
scanf("%d%d", &x, &y);
printf("%d\n", Query(x, y));
}
}
}
return 0;
}
更多推荐
POJ-3580 SuperMemo(Splay树)
发布评论