本文共 6879 字，大约阅读时间需要 22 分钟。
| 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: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
51 2 3 4 52ADD 2 4 1MIN 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#include #include 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;}
转载地址：http://fpwpn.baihongyu.com/