对应POJ题目：点击打开链接
SuperMemo
Time Limit: 5000MSMemory Limit: 65536K
Total Submissions: 11309Accepted: 3545
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
51 2 3 4 52ADD 2 4 1MIN 4 5
Sample Output
5
题意：
对n个数有6种操作：
1）增值：ADD x y D：区间 [x, y] 的所有值增加D
2）翻转：REVERSE x y：把区间 [x, y] 翻转
3）旋转：REVOLVE x y T：对区间 [x, y]顺时针（T > 0）或逆时针（T < 0）旋转T次
4）插入：INSERT x P：在A[x]后面插入P
5）删除：DELETE x：删除A[x]
6）最值：MIN x y：求区间 [x, y] 内的最小值
思路：
Splay树综合操作；需要注意的地方有：
1、Push_down()，Push_up()的写法，应该在什么地方调用
2、旋转操作的T可以是负数
3、旋转其实就是把区间的后一段取下放到前面或着把前一段取下放到后面，不难想明白
#include <cstdio>#include <cstdlib>#include <string>#include <algorithm>#include <string.h>#include <cmath>#include <iostream>#define MIN(x, y) ((x)<(y)?(x):(y))const int MAXN = 100100;using namespace std;typedef int Type;typedef struct TREE{Type val, add, min_v;bool flag;TREE *fa, *l, *r;int sz; //以该结点为根的树的总结点数}Tree;inline void Swap(int &a, int &b){int t = a;a = b;b = t;}class SplayTree{public:SplayTree(){rt = NULL;inf = 1000000000;}void Push_down(Tree *T){if(NULL == T) return;if(T->add){if(T->l){T->l->val += T->add;T->l->add += T->add;T->l->min_v += T->add;}if(T->r){T->r->val += T->add;T->r->add += T->add;T->r->min_v += T->add;}T->add = 0;}if(T->flag){tmp = T->l;T->l = T->r;T->r = tmp;if(T->l) T->l->flag ^= 1;if(T->r) T->r->flag ^= 1;T->flag = 0;}}void Push_up(Tree *T){T->sz = (T->l ? T->l->sz : 0) + (T->r ? T->r->sz : 0) + 1;if(T->l && T->r) T->min_v = MIN(T->val, MIN(T->l->min_v, T->r->min_v));else if(T->l) T->min_v = MIN(T->l->min_v, T->val);else if(T->r) T->min_v = MIN(T->r->min_v, T->val);else T->min_v = T->val; //切记！}void NewNode(Tree *pre, Tree *&T, Type v){T = (Tree *)malloc(sizeof(Tree));T->val = T->min_v = v;T->add = 0;T->flag = 0;T->sz = 1;T->fa = pre;T->l = T->r = NULL;}void MakeTree(Tree *pre, Tree *&T, int x, int y){if(x > y) return;int mid = ((x + y)>>1);NewNode(pre, T, c[mid]);MakeTree(T, T->l, x, mid – 1);MakeTree(T, T->r, mid + 1 , y);Push_up(T);}void Init(int n){int i;for(i = 1; i <= n; i++)scanf("%d", c + i);NewNode(NULL, rt, -inf);NewNode(rt, rt->r, inf);rt->sz = 2;MakeTree(rt->r, rt->r->l, 1, n);Push_up(rt->r);Push_up(rt);}void R_rotate(Tree *x){Tree *y = x->fa;Tree *z = y->fa;Tree *k = x->r;y->l = k;x->r = y;if(z){if(y == z->l) z->l = x;else z->r = x;}if(k) k->fa = y;y->fa = x;x->fa = z;Push_up(y);}void L_rotate(Tree *x){Tree *y = x->fa;Tree *z = y->fa;Tree *k = x->l;y->r = k;x->l = y;if(z){if(y == z->r) z->r = x;else z->l = x;}if(k) k->fa = y;y->fa = x;x->fa = z;Push_up(y);}//寻找第x个数的结点Tree *FindTag(int x){x++;if(NULL == rt) return NULL;Tree *p;p = rt;Push_down(p);Type sum = (p->l ? p->l->sz : 0) + 1;while(sum != x){if(sum < x){p = p->r;x -= sum;}else p = p->l;if(NULL == p) break;Push_down(p);sum = (p->l ? p->l->sz : 0) + 1;}return p;}void Splay(Tree *X, Tree *&T){Tree *p, *end;end = T->fa;while(X->fa != end){p = X->fa;if(end == p->fa){ //p是根结点if(X == p->l) R_rotate(X);else L_rotate(X);break;}//p不是根结点if(X == p->l){if(p == p->fa->l){R_rotate(p); //LLR_rotate(X); //LL}else{R_rotate(X); //RLL_rotate(X);}}else{if(p == p->fa->r){ //RRL_rotate(p);L_rotate(X);}else{ //LRL_rotate(X);R_rotate(X);}}}T = X;Push_up(T);}void Get_interval(int x, int y) //把第x个数转到根，，把第y个数转到根的右儿子{tmp = FindTag(x);Splay(tmp, rt);tmp = FindTag(y);Splay(tmp, rt->r);}void Add(int x, int y, int d){if(x > y) Swap(x, y);Get_interval(x – 1, y + 1);rt->r->l->add += d;rt->r->l->val += d;rt->r->l->min_v += d;Push_up(rt->r);Push_up(rt);}void Reverse(int x, int y){if(x > y) Swap(x, y);Get_interval(x – 1, y + 1);rt->r->l->flag ^= 1;}void Revolve(int x, int y, int t){if(x > y) Swap(x, y);t = t % (y – x + 1); //取模if(t < 0) t += (y – x + 1);if(0 == t) return;Get_interval(y – t, y + 1);Tree *sub = rt->r->l;rt->r->l = NULL;Push_up(rt->r);Push_up(rt);Get_interval(x – 1, x);rt->r->l = sub;sub->fa = rt->r;Push_up(rt->r);Push_up(rt);}void Insert(int pos, int v){Get_interval(pos, pos + 1);NewNode(rt->r, rt->r->l, v);Push_up(rt->r);Push_up(rt);}void Delete(int pos){Get_interval(pos – 1, pos + 1);free(rt->r->l);rt->r->l = NULL;Push_up(rt->r);Push_up(rt);}void Min(int x, int y){if(x > y) Swap(x, y);Get_interval(x – 1, y + 1);Push_down(rt->r->l);printf("%d\n", rt->r->l->min_v);}void Free(){FreeTree(rt);}void FreeTree(Tree *T){if(NULL == T) return;FreeTree(T->l);FreeTree(T->r);free(T);}private:Type c[MAXN], inf;Tree *rt, *tmp;};SplayTree spl;int main(){//freopen("in.txt","r",stdin);int n, m, x, y, z;char ord[10];while(scanf("%d", &n) == 1){spl.Init(n);scanf("%d", &m);while(m–){scanf("%s", ord);if(!strcmp("ADD", ord)){scanf("%d%d%d", &x, &y, &z);spl.Add(x, y, z);}if(!strcmp("REVERSE", ord)){scanf("%d%d", &x, &y);spl.Reverse(x, y);}if(!strcmp("REVOLVE", ord)){scanf("%d%d%d", &x, &y, &z);spl.Revolve(x, y, z);}if(!strcmp("INSERT", ord)){scanf("%d%d", &x, &y);spl.Insert(x, y);}if(!strcmp("DELETE", ord)){scanf("%d", &x);spl.Delete(x);}if(!strcmp("MIN", ord)){scanf("%d%d", &x, &y);spl.Min(x, y);}}spl.Free();}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
不要轻言放弃，否则对不起自己
