【模板库】Splay

参考例题：http://www.lydsy.com/JudgeOnline/problem.php?id=1895

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int INF = 0x7fffffff;
const int N = 200009;
  
inline int read() {
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
    return ret*f;
}
  
class Splay{
    struct Node{int ch[2],val,mn,sz,fa,delta,rev;}p[N]; int cnt;
    public:
        inline Splay() { //init the splay and place begining(1) and ending(2) of the sequence
            cnt = 2; p[1].ch[1] = 2;
            p[1].val = p[1].mn = INF;
            p[2].val = p[2].mn = INF;
            p[1].sz = 2; p[2].sz = 1;
            p[1].fa = p[2].fa = 1;
        }
        inline void insert(int pos, int v) { ++pos; //insert a new node with value v as ths (pos + 1) node
            int w; splay(w=rank(1, pos), 1);
            int nw; splay(nw=rank(1, pos+1), w);
            p[nw].ch[0] = ++cnt; p[cnt].fa = nw;
            p[cnt].mn = p[cnt].val = v; p[cnt].sz = 1;
            maintain(nw); maintain(w); maintain(1);
        }
        inline void add(int l, int r, int v) { ++l; ++r; //add value v to elements of range[l,r]
            int w; splay(w=rank(1, l-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[p[nw].ch[0]].delta += v; 
            PushDown(p[nw].ch[0]); maintain(nw);
            maintain(w); maintain(1); 
        }
        inline int query(int l, int r) { ++l; ++r; //query the min element in range[l,r]
            int w; splay(w=rank(1, l-1), 1); 
            int nw; splay(nw=rank(1, r+1), w);
            return PushDown(p[nw].ch[0]), p[p[nw].ch[0]].mn;
        }
        inline void remove(int r) { ++r; //remove the r node
            int w; splay(w=rank(1, r-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[nw].ch[0] = 0; maintain(nw);
            maintain(w); maintain(1);
        } 
        inline void reverse(int l, int r) { ++l; ++r; //reverse the elements in range[l,r]
            int w; splay(w=rank(1, l-1), 1);
            int nw; splay(nw=rank(1, r+1), w);
            p[p[nw].ch[0]].rev ^= 1;
        }
        inline void Rotate(int l, int r, int t) { //rotate the elements in range[l,r] t steps
            if (l==r||!(t%=((++r) - (++l) + 1))) return;
            int w; splay(w=rank(1, l-1), 1); 
            int nw; splay(nw=rank(1, r+1), w);
            int nnw; splay(nnw=rank(p[nw].ch[0], r-l-t+1), nw); 
            int nnnw; splay(nnnw=rank(p[nnw].ch[1], t), nnw); 
            p[nw].ch[0] = nnnw; p[nnnw].ch[1] = nnw; p[nnw].ch[1] = 0;
            p[nnw].fa = nnnw; p[nnnw].fa = nw;
            maintain(nnw); maintain(nnnw); 
        }
    private:
        inline void PushDown(int w) {
            if (p[w].delta) {
                p[w].mn += p[w].delta; p[w].val += p[w].delta;
                p[p[w].ch[1]].delta += p[w].delta;
                p[p[w].ch[0]].delta += p[w].delta;
                p[w].delta = 0;
            }
            if (p[w].rev) {
                swap(p[w].ch[0], p[w].ch[1]); p[w].rev = 0;
                p[p[w].ch[0]].rev ^= 1; p[p[w].ch[1]].rev ^= 1;
            }
        }
        inline void maintain(int w) {
            p[w].mn = p[w].val; p[w].sz = p[p[w].ch[0]].sz + p[p[w].ch[1]].sz + 1;
            if (p[w].ch[0]) PushDown(p[w].ch[0]), p[w].mn = min(p[w].mn, p[p[w].ch[0]].mn);
            if (p[w].ch[1]) PushDown(p[w].ch[1]), p[w].mn = min(p[w].mn, p[p[w].ch[1]].mn); 
        }
        inline void rotate(int w) { //rotate w to its father
            int f=p[w].fa,t=p[f].ch[1]==w,ff=p[f].fa; 
            p[f].ch[t] = p[w].ch[t^1]; p[p[w].ch[t^1]].fa = f;
            p[w].ch[t^1] = f; p[w].fa = p[f].fa; p[f].fa = w; 
            if (ff != f) p[ff].ch[p[ff].ch[1]==f] = w;
            maintain(f); maintain(w);
        }
        inline void splay(int w, int pur) { //splay w to pur's son
            if (w == pur) return;
            for (int f,ff;f=p[w].fa,p[w].fa!=pur;) {
                ((ff=p[f].fa) == pur)? rotate(w):
                (((p[f].ch[1]==w)^(p[ff].ch[1]==f))?rotate(w),rotate(f):rotate(f),rotate(w));
            }
        }
        int rank(int w, int t) { //function rank is needed to be called before each splay operation to push down tags
            PushDown(w); if (t<=0) return w; int szt = p[p[w].ch[0]].sz;
            if (szt >= t) return rank(p[w].ch[0], t);
            else if (szt + 1 == t) return w;
            else return rank(p[w].ch[1], t-1-szt);
        }
}SP; 
  
int main() {
    int n = read(); char opt[10]; 
    for (int i=1;i<=n;i++) SP.insert(i-1, read());
    for (int m=read(),l,r,x;m;--m) {
        scanf("%s",opt+1);
        if (opt[1] == 'A') {
            l = read(); r = read();
            SP.add(l, r, read());
        } else if (opt[1] == 'R' && opt[4] == 'E') {
            l = read(); r = read();
            SP.reverse(l, r);
        } else if (opt[1] == 'R') {
            l = read(); r = read();
            SP.Rotate(l, r, read());
        } else if (opt[1] == 'I') {
            l = read(); r = read();
            SP.insert(l, r);
        } else if (opt[1] == 'D') {
            SP.remove(read());
        } else {
            l = read(); r = read();
            printf("%d\n",SP.query(l,r));
        } 
    }
    return 0;
}