http://poj.org/problem?id=3580
题意：有6种操作，其中有两种之前没做过，就是Revolve操作和Min操作。Revolve一开始想着一个一个删一个一个插，觉得太暴力了，后来发现可以把要放到前面的一段切开，丢到前面去，就和上一题的Cut是一样的了。还有Min操作，一开始特别ZZ地想着只要找keytree的最左边就好了，然后发现并不是那样的，要维护一个 mi 值，一开始两个节点设成 INF，然后 pushup 的时候先把 val 赋给 mi，然后再和左右儿子对比。WA了好几次，找了下数据。。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <map>
#include <queue>
using namespace std;
#define N 1000100
#define INF 0x7fffffff
#define lson ch[x][0]
#define rson ch[x][1]
#define keytree ch[ch[root][1]][0] struct SplayTree
{
int num[N], rev[N], ch[N][], fa[N], val[N], sz[N], col[N], mi[N];
int n, root, cnt; void PushDown(int x)
{
if(rev[x]) {
swap(lson, rson);
if(lson) rev[lson] ^= ;
if(rson) rev[rson] ^= ;
rev[x] = ;
}
if(col[x]) {
if(lson) {
col[lson] += col[x];
val[lson] += col[x];
mi[lson] += col[x];
}
if(rson) {
col[rson] += col[x];
val[rson] += col[x];
mi[rson] += col[x];
}
col[x] = ;
}
} void PushUp(int x)
{
sz[x] = sz[lson] + sz[rson] + ;
mi[x] = val[x];
if(lson) mi[x] = min(mi[x], mi[lson]);
if(rson) mi[x] = min(mi[x], mi[rson]);
} int NewNode(int w, int f, int kind)
{
int x = ++cnt;
ch[x][] = ch[x][] = rev[x] = col[x] = ;
sz[x] = ; val[x] = w; fa[x] = f;
mi[x] = w;
ch[f][kind] = cnt;
return x;
} void Build(int l, int r, int &x, int f, int kind)
{
if(l > r) return ;
int m = (l + r) >> ;
x = NewNode(num[m], f, kind);
Build(l, m - , ch[x][], x, );
Build(m + , r, ch[x][], x, );
PushUp(x);
} void Init()
{
root = cnt = ;
rev[] = val[] = col[] = fa[] = sz[] = ch[][] = ch[][] = ;
mi[] = INF;
root = NewNode(INF, , );
ch[root][] = NewNode(INF, root, );
val[ch[root][]] = INF;
sz[root] = ;
Build(, n, keytree, ch[root][], );
PushUp(ch[root][]); PushUp(root);
} void Rotate(int x, int kind)
{
int y = fa[x], z = fa[y];
PushDown(y); PushDown(x);
ch[y][!kind] = ch[x][kind];
if(ch[y][!kind]) fa[ch[y][!kind]] = y;
if(z) {
if(y == ch[z][]) ch[z][] = x;
else ch[z][] = x;
}
fa[x] = z; fa[y] = x;
ch[x][kind] = y;
PushUp(y);
} void Splay(int x, int goal)
{
// printf("%d, %d\n", x, fa[x]);
PushDown(x);
while(fa[x] != goal) {
int y = fa[x], z = fa[y];
PushDown(z); PushDown(y); PushDown(x);
int kind1 = x == ch[y][];
int kind2 = y == ch[z][];
if(z == goal) {
Rotate(x, kind1);
} else {
if(kind1 == kind2) {
Rotate(y, kind1);
} else {
Rotate(x, kind1);
}
Rotate(x, kind2);
}
}
PushUp(x);
if(goal == ) root = x;
} void RTO(int k, int goal)
{
int x = root;
PushDown(x);
while(k != sz[lson] + ) {
if(k <= sz[lson]) x = lson;
else k -= sz[lson] + , x = rson;
PushDown(x);
}
// printf("%d, %d, %d\n", x, val[x], goal);
Splay(x, goal);
} void Add(int l, int r, int d)
{
RTO(l, ); RTO(r + , root);
col[keytree] += d;
val[keytree] += d;
mi[keytree] += d;
PushUp(ch[root][]); PushUp(root);
} void Reverse(int l, int r)
{
RTO(l, ); RTO(r + , root);
rev[keytree] ^= ;
PushUp(ch[root][]); PushUp(root);
} void Cut(int l, int r, int c)
{
RTO(l, ); RTO(r + , root);
PushUp(ch[root][]); PushUp(root);
// Debug();
// puts("---------");
int tmp = keytree;
keytree = ;
RTO(c, ); RTO(c + , root);
keytree = tmp;
fa[tmp] = ch[root][];
PushUp(ch[root][]); PushUp(root);
} void Revolve(int l, int r, int t)
{
t = (t % (r - l + ) + (r - l + )) % (r - l + );
if(t == ) return ;
Cut(r - t + , r, l);
// Debug();
PushUp(ch[root][]); PushUp(root);
} void Insert(int index, int w)
{
RTO(index + , ); RTO(index + , root);
keytree = NewNode(w, ch[root][], );
PushUp(ch[root][]); PushUp(root);
} void Delete(int index)
{
RTO(index, ); RTO(index + , root);
keytree = ;
PushUp(ch[root][]); PushUp(root);
} int Query(int l, int r)
{
RTO(l, );
RTO(r + , root);
// Debug();
return mi[keytree];
} void Travel(int x)
{
if(lson) Travel(lson);
printf("ttt : %d, %d, %d\n", x, val[x], mi[x]);
if(rson) Travel(rson);
} void Debug()
{
Travel(root);
}
}spy; int main()
{
int n;
while(~scanf("%d", &n)) {
spy.n = n;
for(int i = ; i <= n; i++) scanf("%d", &spy.num[i]);
spy.Init();
int m;
scanf("%d", &m);
while(m--) {
char s[];
int a, b, c;
scanf("%s", s);
if(s[] == 'A') {
scanf("%d%d%d", &a, &b, &c);
spy.Add(a, b, c);
} else if(s[] == 'M') {
scanf("%d%d", &a, &b);
printf("%d\n", spy.Query(a, b));
} else if(s[] == 'R' && s[] == 'E') {
scanf("%d%d", &a, &b);
spy.Reverse(a, b);
} else if(s[] == 'R' && s[] == 'O') {
scanf("%d%d%d", &a, &b, &c);
spy.Revolve(a, b, c);
} else if(s[] == 'I') {
scanf("%d%d", &a, &b);
spy.Insert(a, b);
} else if(s[] == 'D') {
scanf("%d", &a);
spy.Delete(a);
}
// spy.Debug();
}
}
return ;
} /*
5
1
2
3
4
5
2
REVOLVE 1 5 4
MIN 4 5 10
1 2 3 4 5 6 7 8 9 10
15
ADD 4 8 3
MIN 5 7
MIN 7 10
REVERSE 2 5
MIN 2 6
MIN 2 3
INSERT 3 4
MIN 3 4
MIN 5 10
DELETE 6
MIN 3 5
MIN 4 4
REVOLVE 3 6 7
MIN 5 8
MIN 7 10
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
８
９
２
７
４
２
３
４
７
９
*/