Splay

参考：

普通模板：

const int N = 1e5 + 10;int ch[N][2], val[N], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;int n, m;inline int ck(int x) {    return ch[fa[x]][1] == x;}inline void push_up(int x) {    sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}///区间反转inline void push_down(int x) {    if(lazy[x]) {        swap(ch[x][0], ch[x][1]);        lazy[ch[x][0]] ^= 1;        lazy[ch[x][1]] ^= 1;        lazy[x] = 0;    }}void Rotate(int x) {    int y = fa[x], z = fa[y];    push_down(y), push_down(x);///区间反转    int k = ck(x), w = ch[x][k^1];    ch[y][k] = w, fa[w] = y;    ch[z][ck(y)] = x, fa[x] = z;    ch[x][k^1] = y, fa[y] = x;    push_up(y), push_up(x);}void Splay(int x, int goal = 0) {    push_down(x);///区间反转    while(fa[x] != goal) {        int y = fa[x], z = fa[y];        if(z != goal) {            if(ck(x) == ck(y)) Rotate(y);            else Rotate(x);        }        Rotate(x);    }    if(!goal) rt = x;}void Find(int x) {    if(!rt) return ;    int cur = rt;    while(ch[cur][x>val[cur]] && x != val[cur]) cur = ch[cur][x>val[cur]];    Splay(cur);}void Insert(int x) {    int cur = rt, p = 0;    while(cur && val[cur] != x) {        p = cur;        cur = ch[cur][x>val[cur]];    }    if(cur) cnt[cur]++;    else {        cur = ++ncnt;        if(p) ch[p][x>val[p]] = cur;        fa[cur] = p;        ch[cur][0] = ch[cur][1] = 0;        val[cur] = x;        cnt[cur] = sz[cur] = 1;    }    Splay(cur);}int Kth(int k) {    int cur = rt;    while(true) {        push_down(cur); ///区间反转        if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0];        else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1];        else return cur;    }}inline int get_min(int x) {    while(x && ch[x][0]) x = ch[x][0];    return x;}inline int get_max(int x) {    while(x && ch[x][1]) x = ch[x][1];    return x;}int Pre(int x) {    Find(x);    if(val[rt] < x) return rt;    int cur = ch[rt][0];    while(ch[cur][1]) cur = ch[cur][1];    return cur;}int Succ(int x) {    Find(x);    if(val[rt] > x) return rt;    int cur = ch[rt][1];    while(ch[cur][0]) cur = ch[cur][0];    return cur;}void Remove(int x) {    int last = Pre(x), next = Succ(x);    Splay(last), Splay(next, last);    int del = ch[next][0];    if(cnt[del] > 1) cnt[del]--, Splay(del);    else ch[next][0] = 0, push_up(next), push_up(last);}///区间反转void Reverse(int l, int r) {    int x = Kth(l), y = Kth(r+2);    Splay(x), Splay(y, x);    lazy[ch[y][0]] ^= 1;}void Output(int x) {    push_down(x);    if(ch[x][0]) Output(ch[x][0]);    if(1 <= val[x] && val[x] <= n) printf("%d ", val[x]);    if(ch[x][1]) Output(ch[x][1]);}void delete_root() {    if(ch[rt][1]) {        int cur = ch[rt][1];        while(cur && ch[cur][0]) cur = ch[cur][0];        Splay(cur, rt);        ch[cur][0] = ch[rt][0];        fa[ch[cur][0]] = cur;        rt = cur;    }    else rt = ch[rt][0];    fa[rt] = 0;    if(rt) push_up(rt);}inline int NewNode(int x) {    int cur;    if(q.empty()) cur = ++ncnt;    else cur = q.front(), q.pop();    ///初始化    ch[cur][0] = ch[cur][1] = fa[cur] = lazy[cur] = 0;    val[cur] = x;    sz[cur] = cnt[cur] = 1;    return cur;}void Recycle(int x) {    if(ch[x][0]) Recycle(ch[x][0]);    if(ch[x][1]) Recycle(ch[x][1]);    if(x) q.push(x);}int build(int l, int r, int *a) {    if(l > r) return 0;    int mid = l+r >> 1, cur = NewNode(a[mid]);    if(l == r) return cur;    if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur;    if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur;    push_up(cur);    return cur;}inline void init() {    ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = sz[0] = cnt[0] = val[0] = lazy[0] = 0;}

按排名插入模板（常数较小？？？也许以前的方法写搓了）：

inline void Newnode(int &cur, int f, int a) {    cur = ++ncnt;    fa[cur] = f;    val[cur] = a;    ch[cur][0] = ch[cur][1] = 0;    sz[cur] = cnt[cur] = 1;}void Insert(int x, int y) {    int p = 0;    if(!rt) {        Newnode(rt, 0, y);        return ;    }    if(!x) {        p = rt;        sz[p]++;        while(ch[p][0]) p = ch[p][0], sz[p]++;        Newnode(ch[p][0], p, y);        Splay(ch[p][0]);        return ;    }    int u = Kth(x);    Splay(u);    Newnode(rt, 0, y);    ch[rt][1] = ch[u][1];    fa[ch[rt][1]] = rt;    ch[u][1] = 0;    ch[rt][0] = u;    fa[u] = rt;    push_up(u), push_up(rt);}

例题：

 

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdd pair
           
            #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 2e5 + 10;int ch[N][2], val[N], cnt[N], fa[N], sz[N], ncnt = 0, rt = 0;inline int ck(int x) { return ch[fa[x]][1] == x;}inline void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}void Rotate(int x) { int y = fa[x], z = fa[y], k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x);}void Splay(int x, int goal = 0) { while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}void Find(int x) { if(!rt) return ; int cur = rt; while(ch[cur][x>val[cur]] && x != val[cur]) cur = ch[cur][x>val[cur]]; Splay(cur);}void Insert(int x) { int cur = rt, p = 0; while(cur && val[cur] != x) { p = cur; cur = ch[cur][x>val[cur]]; } if(cur) cnt[cur]++; else { cur = ++ncnt; if(p) ch[p][x>val[p]] = cur; fa[cur] = p; ch[cur][0] = ch[cur][1] = 0; val[cur] = x; cnt[cur] = sz[cur] = 1; } Splay(cur);}int Kth(int k) { int cur = rt; while(true) { if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; }}int Pre(int x) { Find(x); if(val[rt] < x) return rt; int cur = ch[rt][0]; while(ch[cur][1]) cur = ch[cur][1]; return cur;}int Succ(int x) { Find(x); if(val[rt] > x) return rt; int cur = ch[rt][1]; while(ch[cur][0]) cur = ch[cur][0]; return cur;}void Remove(int x) { int last = Pre(x), next = Succ(x); Splay(last), Splay(next, last); int del = ch[next][0]; if(cnt[del] > 1) cnt[del]--, Splay(del); else ch[next][0] = 0/*, push_up(next), push_up(last)*/;}int n, opt, x;int main() { Insert(INT_MIN); Insert(INT_MAX); scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d %d", &opt, &x); if(opt == 1) Insert(x); else if(opt == 2) Remove(x); else if(opt == 3) Find(x), printf("%d\n", sz[ch[rt][0]]); else if(opt == 4) printf("%d\n", val[Kth(x+1)]); else if(opt == 5) printf("%d\n", val[Pre(x)]); else printf("%d\n", val[Succ(x)]); } return 0;}
           
          
         
        
       
      

 

思路：跟区间反转相关的Splay维护的都是下标

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdd pair
           
            #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 1e5 + 10;int ch[N][2], val[N], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;int n, m;inline int ck(int x) { return ch[fa[x]][1] == x;}inline void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}///区间反转inline void push_down(int x) { if(lazy[x]) { swap(ch[x][0], ch[x][1]); lazy[ch[x][0]] ^= 1; lazy[ch[x][1]] ^= 1; lazy[x] = 0; }}void Rotate(int x) { int y = fa[x], z = fa[y], k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x);}void Splay(int x, int goal = 0) { while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}void Find(int x) { if(!rt) return ; int cur = rt; while(ch[cur][x>val[cur]] && x != val[cur]) cur = ch[cur][x>val[cur]]; Splay(cur);}void Insert(int x) { int cur = rt, p = 0; while(cur && val[cur] != x) { p = cur; cur = ch[cur][x>val[cur]]; } if(cur) cnt[cur]++; else { cur = ++ncnt; if(p) ch[p][x>val[p]] = cur; fa[cur] = p; ch[cur][0] = ch[cur][1] = 0; val[cur] = x; cnt[cur] = sz[cur] = 1; } Splay(cur);}int Kth(int k) { int cur = rt; while(true) { push_down(cur); ///区间反转 if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; }}int Pre(int x) { Find(x); if(val[rt] < x) return rt; int cur = ch[rt][0]; while(ch[cur][1]) cur = ch[cur][1]; return cur;}int Succ(int x) { Find(x); if(val[rt] > x) return rt; int cur = ch[rt][1]; while(ch[cur][0]) cur = ch[cur][0]; return cur;}void Remove(int x) { int last = Pre(x), next = Succ(x); Splay(last), Splay(next, last); int del = ch[next][0]; if(cnt[del] > 1) cnt[del]--, Splay(del); else ch[next][0] = 0, push_up(next), push_up(last);}///区间反转void Reverse(int l, int r) { int x = Kth(l), y = Kth(r+2); Splay(x), Splay(y, x); lazy[ch[y][0]] ^= 1;}void Output(int x) { push_down(x); if(ch[x][0]) Output(ch[x][0]); if(1 <= val[x] && val[x] <= n) printf("%d ", val[x]); if(ch[x][1]) Output(ch[x][1]);}int l, r;int main() { scanf("%d %d", &n, &m); for (int i = 0; i <= n+1; ++i) Insert(i); while(m--) { scanf("%d %d", &l, &r); Reverse(l, r); } Output(rt); return 0;}
           
          
         
        
       
      

 

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdd pair
           
            #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 1e6 + 10;int ch[N][2], val[N], cnt[N], fa[N], sz[N], rev[N], lazy[N], ncnt = 0, rt = 0;int n, m, a[N], lmx[N], rmx[N], mx[N], sm[N];queue
            
              q;inline int NewNode(int x) { int cur; if(q.empty()) cur = ++ncnt; else cur = q.front(), q.pop(); ch[cur][0] = ch[cur][1] = fa[cur] = 0; rev[cur] = lazy[cur] = 0; sz[cur] = cnt[cur] = 1; mx[cur] = sm[cur] = val[cur] = x; lmx[cur] = rmx[cur] = max(0, x); return cur;}void Recycle(int x) { if(ch[x][0]) Recycle(ch[x][0]); if(ch[x][1]) Recycle(ch[x][1]); if(x) q.push(x);}inline void push_up(int x) { int l = ch[x][0], r = ch[x][1]; sz[x] = sz[l] + cnt[x] + sz[r]; sm[x] = sm[l] + val[x] + sm[r]; lmx[x] = max(lmx[l], sm[l] + val[x] + lmx[r]); rmx[x] = max(rmx[r], sm[r] + val[x] + rmx[l]); mx[x] = max(rmx[l] + val[x] + lmx[r], max(mx[l], mx[r]));}inline void push_down(int x) { int l = ch[x][0], r = ch[x][1]; if(lazy[x]) { lazy[x] = rev[x] = 0; if(l) { lazy[l] = 1; val[l] = val[x]; sm[l] = val[l] * sz[l]; lmx[l] = rmx[l] = max(0, sm[l]); mx[l] = sm[l] > 0 ? sm[l] : val[l]; } if(r) { lazy[r] = 1; val[r] = val[x]; sm[r] = val[r] * sz[r]; lmx[r] = rmx[r] = max(0, sm[r]); mx[r] = sm[r] > 0 ? sm[r] : val[r]; } } if(rev[x]) { rev[l] ^= 1, rev[r] ^= 1, rev[x] = 0; swap(lmx[l], rmx[l]); swap(lmx[r], rmx[r]); swap(ch[l][0], ch[l][1]); swap(ch[r][0], ch[r][1]); }}int build(int l, int r, int *a) { if(l > r) return 0; int mid = l+r >> 1, cur = NewNode(a[mid]); if(l == r) return cur; if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur; if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur; push_up(cur); return cur;}inline int ck(int x) { return ch[fa[x]][1] == x;}void Rotate(int x) { int y = fa[x], z = fa[y], k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x);}void Splay(int x, int goal = 0) { while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}int Kth(int k) { int cur = rt; while(true) { push_down(cur); ///区间反转 if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; }}///区间反转void Reverse(int x, int y) { int u = Kth(x), v = Kth(x+y+1); Splay(u), Splay(v, u); int son = ch[v][0]; if(!lazy[son]) { rev[son] ^= 1; swap(ch[son][0], ch[son][1]); swap(lmx[son], rmx[son]); } push_up(v), push_up(u);}void Insert(int x, int y) { for (int i = 1; i <= y; ++i) scanf("%d", &a[i]); int u = Kth(x+1), v = Kth(x+2); Splay(u), Splay(v, u); int cur = build(1, y, a); ch[v][0] = cur, fa[cur] = v; push_up(v), push_up(u);}void Delete(int x, int y) { int u = Kth(x), v = Kth(x+y+1); Splay(u), Splay(v, u); Recycle(ch[v][0]); ch[v][0] = 0; push_up(v), push_up(u);}void Make_Same(int x, int y, int z) { int u = Kth(x), v = Kth(x+y+1); Splay(u), Splay(v, u); int son = ch[v][0]; lazy[son] = 1; val[son] = z; sm[son] = z*sz[son]; mx[son] = sm[son] > 0 ? sm[son] : val[son]; lmx[son] = rmx[son] = max(0, sm[son]); push_up(v), push_up(u);}int Get_Sum(int x, int y) { int u = Kth(x), v = Kth(x+y+1); Splay(u), Splay(v, u); push_up(v), push_up(u); return sm[ch[v][0]];}char opt[20];int x, y, z;int main() { scanf("%d %d", &n, &m); for (int i = 2; i <= n+1; ++i) scanf("%d", &a[i]); a[1] = a[n+2] = mx[0] = -2000; rt = build(1, n+2, a); for (int i = 0; i < m; ++i) { scanf("%s", opt); if(opt[0] == 'I') { scanf("%d %d", &x, &y); Insert(x, y); } else if(opt[0] == 'D') { scanf("%d %d", &x, &y); Delete(x, y); } else if(opt[0] == 'M' && opt[5] == 'S') { scanf("%d %d %d", &x, &y, &z); Make_Same(x, y, z); } else if(opt[0] == 'R') { scanf("%d %d", &x, &y); Reverse(x, y); } else if(opt[0] == 'G') { scanf("%d %d", &x, &y); printf("%d\n", Get_Sum(x, y)); } else printf("%d\n", mx[rt]); } return 0;}
            
           
          
         
        
       
      

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       #include
       
        using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
        
         #define pli pair
         
          #define pii pair
          
           #define piii pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";const int N = 1e6 + 10;int ch[N][2], val[N], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;int a[N];inline int ck(int x) { return ch[fa[x]][1] == x;}inline void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}void Rotate(int x) { int y = fa[x], z = fa[y], k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x);}void Splay(int x, int goal = 0) { while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}void Find(int x) { if(!rt) return ; int cur = rt; while(ch[cur][x>val[cur]] && x != val[cur]) cur = ch[cur][x>val[cur]]; Splay(cur);}void Insert(int x, int id) { int cur = rt, p = 0; while(cur && val[cur] != x) { p = cur; cur = ch[cur][x>val[cur]]; } if(cur) cnt[cur]++; else { cur = ++ncnt; if(p) ch[p][x>val[p]] = cur; fa[cur] = p; ch[cur][0] = ch[cur][1] = 0; val[cur] = x; a[cur] = id; cnt[cur] = sz[cur] = 1; } Splay(cur);}int Kth(int k) { int cur = rt; while(true) { if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; }}int Pre(int x) { Find(x); if(val[rt] < x) return rt; int cur = ch[rt][0]; while(ch[cur][1]) cur = ch[cur][1]; return cur;}int Succ(int x) { Find(x); if(val[rt] > x) return rt; int cur = ch[rt][1]; while(ch[cur][0]) cur = ch[cur][0]; return cur;}void Remove(int x) { int last = Pre(x), next = Succ(x); Splay(last), Splay(next, last); int del = ch[next][0]; if(cnt[del] > 1) cnt[del]--, Splay(del); else ch[next][0] = 0, push_up(next), push_up(last);}int ty, k, p;int main() { int now = 0; Insert(-100, 0); Insert(10000010, 0); while(~scanf("%d", &ty) && ty) { if(ty == 1) { scanf("%d %d", &k, &p); Insert(p, k); ++now; } else if(ty == 2) { if(!now) { printf("0\n"); continue; } int cur = Kth(now+1); printf("%d\n", a[cur]); --now; Remove(val[cur]); } else if(ty == 3) { if(!now) { printf("0\n"); continue; } int cur = Kth(2); printf("%d\n", a[cur]); --now; Remove(val[cur]); } } return 0;}
            
           
          
         
        
       
      

Splay代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       #include
       
        using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
        
         #define pli pair
         
          #define pii pair
          
           #define piii pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 2e5 + 10;int ch[N][2], val[N], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;int n, m, a[N];inline int ck(int x) { return ch[fa[x]][1] == x;}inline void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}void Rotate(int x) { int y = fa[x], z = fa[y], k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x);}void Splay(int x, int goal = 0) { while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}inline int Kth(int k) { int cur = rt; while(true) { if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; }}inline void Newnode(int &cur, int f, int a) { cur = ++ncnt; fa[cur] = f; val[cur] = a; ch[cur][0] = ch[cur][1] = 0; sz[cur] = cnt[cur] = 1;}void Insert(int x, int y) { int p = 0; if(!rt) { Newnode(rt, 0, y); return ; } if(!x) { p = rt; sz[p]++; while(ch[p][0]) p = ch[p][0], sz[p]++; Newnode(ch[p][0], p, y); Splay(ch[p][0]); return ; } int u = Kth(x); Splay(u); Newnode(rt, 0, y); ch[rt][1] = ch[u][1]; fa[ch[rt][1]] = rt; ch[u][1] = 0; ch[rt][0] = u; fa[u] = rt; push_up(u), push_up(rt);}void Output(int x) { if(ch[x][0]) Output(ch[x][0]); printf("%d ", val[x]); if(ch[x][1]) Output(ch[x][1]);}int x, y;int main() { while(~scanf("%d", &n)) { ncnt = rt = 0; for (int i = 1; i <= n; ++i) { scanf("%d %d", &x, &y); Insert(x, y); } Output(rt); printf("\n"); } return 0;}
            
           
          
         
        
       
      

树状数组代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
          
           #define pli pair
           
            #define pii pair
            
             #define piii pair
             
              #define pdd pair
              
               #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 4e5 + 5;int n, bit[N], res[N];pii a[N];void add(int x, int a) { while(x <= n) bit[x] += a, x += x&-x;}int Kth(int k) { int up = log(n)/log(2); int res = 0; for (int i = up; i >= 0; --i) { if(res + (1<
               
                 n) continue; if(bit[res+(1<
                
                 < k) { res += 1<
                 
                  = 1; --i) { int pos = Kth(a[i].fi+1); res[pos] = a[i].se; add(pos, -1); } for (int i = 1; i <= n; ++i) printf("%d%c", res[i], " \n"[i==n]); for (int i = 0; i <= n; ++i) bit[i] = 0; } return 0;}
                 
                
               
              
             
            
           
          
         
        
       
      

思路：按下标建树，每次将要翻转到前面的节点Splay到根上，将它的左儿子打上标记，然后把根删掉。

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdi pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 1e5 + 5;int ch[N][2], val[N], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;int n, m, a[N], id[N], node[N], ans[N];pii t[N];inline int ck(int x) { return ch[fa[x]][1] == x;}inline void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}///区间反转inline void push_down(int x) { if(lazy[x]) { swap(ch[x][0], ch[x][1]); lazy[ch[x][0]] ^= 1; lazy[ch[x][1]] ^= 1; lazy[x] = 0; }}void Rotate(int x) { int y = fa[x], z = fa[y]; push_down(y), push_down(x); int k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x);}void Splay(int x, int goal = 0) { push_down(x); while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}int Kth(int k) { int cur = rt; while(true) { push_down(cur); ///区间反转 if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; }}int Newnode(int x) { int cur = ++ncnt; ch[cur][0] = ch[cur][1] = fa[cur] = 0; val[cur] = x; cnt[cur] = sz[cur] = 1; lazy[cur] = 0; return cur;}int build(int l, int r, int *a) { if(l > r) return 0; int mid = l+r >> 1, cur = Newnode(a[mid]); node[id[mid]] = cur; if(l == r) return cur; if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur; if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur; push_up(cur); return cur;}void delete_root() { int old = rt; if(ch[rt][1]) { rt = ch[rt][1]; Splay(Kth(1)); ch[rt][0] = ch[old][0]; fa[ch[rt][0]] = rt; } else rt = ch[rt][0]; fa[rt] = 0; push_up(rt);}int main() { while(~scanf("%d", &n)) { if(n == 0) break; for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); t[i].fi = a[i]; t[i].se = i; } sort(t+1, t+1+n); for (int i = 1; i <= n; ++i) id[t[i].se] = i; rt = ncnt = 0; sz[0] = cnt[0] = ch[0][0] = ch[0][1] = fa[0] = lazy[0] = 0; rt = build(1, n, a); for (int i = 1; i <= n; ++i) { Splay(node[i]); printf("%d%c", sz[ch[rt][0]]+i, " \n"[i==n]); lazy[ch[rt][0]] ^= 1; delete_root(); } } return 0;}
            
           
          
         
        
       
      

 

思路：先把TOP操作和QUERY操作的值单独扣出来，然后其他的一段区间看成一个节点

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
             
              #define pli pair
              
               #define pii pair
               
                #define piii pair
                
                 #define pdi pair
                 
                  #define pdd pair
                  
                   #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 2e5 + 1000;int ch[N][2], st[N], cnt[N], fa[N], sz[N], ncnt = 0, rt = 0;int n, m;int T, op[N/2], a[N/2], node[N], tot, vc[N/2], tmp;pii t[N];char s[100];inline int ck(int x) { return ch[fa[x]][1] == x;}inline void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}void Rotate(int x) { int y = fa[x], z = fa[y], k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x);}void Splay(int x, int goal = 0) { while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}inline int Kth(int k) { int cur = rt; while(true) { if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; }}inline int KTH(int k) { int cur = rt; while(true) { if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return st[cur] + k-sz[ch[cur][0]]-1; }}inline void delete_root() { if(ch[rt][1]) { int cur = ch[rt][1]; while(cur && ch[cur][0]) cur = ch[cur][0]; Splay(cur, rt); ch[cur][0] = ch[rt][0]; fa[ch[cur][0]] = cur; rt = cur; } else rt = ch[rt][0]; fa[rt] = 0; if(rt) push_up(rt);}inline int NewNode(pii x) { int cur = ++ncnt; ch[cur][0] = ch[cur][1] = fa[cur] = 0; st[cur] = x.fi; cnt[cur] = sz[cur] = x.se - x.fi + 1; return cur;}int build(int l, int r) { if(l > r) return 0; int mid = l+r >> 1, cur = NewNode(t[mid]); node[mid] = cur; if(l == r) return cur; ch[cur][0] = build(l, mid-1); if(ch[cur][0]) fa[ch[cur][0]] = cur; ch[cur][1] = build(mid+1, r); if(ch[cur][1]) fa[ch[cur][1]] = cur; push_up(cur); return cur;}inline int get(int x) { int l = 1, r = tot, m = l+r >> 1; while(l <= r) { if(t[m].fi > x) r = m-1; else if(t[m].se < x) l = m+1; else return node[m]; m = l+r >> 1; }}inline void init() { tmp = 1; tot = 0; ncnt = rt = 0; ch[0][0] = ch[0][1] = st[0] = cnt[0] = fa[0] = sz[0] = 0;}int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout); scanf("%d", &T); for (int cs = 1; cs <= T; ++cs) { init(); scanf("%d %d", &n, &m); for (int i = 1; i <= m; ++i) { scanf("%s%d", s, &a[i]); if(s[0] == 'T') op[i] = 1, vc[tmp++] = a[i]; else if(s[0] == 'Q') op[i] = 2, vc[tmp++] = a[i]; else op[i] = 3; } vc[tmp++] = n; sort(vc, vc+tmp); tmp = unique(vc, vc+tmp) - vc; for (int i = 1; i < tmp; ++i) { if(vc[i]-vc[i-1] > 1) t[++tot].fi = vc[i-1]+1, t[tot].se = vc[i]-1; t[++tot].fi = vc[i], t[tot].se = vc[i]; } rt = build(1, tot); printf("Case %d:\n", cs); for (int i = 1; i <= m; ++i) { if(op[i] == 1) { int cur = get(a[i]); Splay(cur); delete_root(); int now = rt; while(now && ch[now][0]) now = ch[now][0]; ch[now][0] = cur; fa[cur] = now; st[cur] = a[i]; sz[cur] = cnt[cur] = 1; ch[cur][0] = ch[cur][1] = 0; Splay(cur); } else if(op[i] == 2) { int cur = get(a[i]); Splay(cur); printf("%d\n", sz[ch[cur][0]]+1); } else printf("%d\n", KTH(a[i])); } } return 0;}
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

思路：常规操作

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdi pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 3e5 + 50;int ch[N][2], val[N], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;int n, m;int T, a[N], x, y, z, tmp;char s[100];inline int ck(int x) { return ch[fa[x]][1] == x;}inline void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}///区间反转inline void push_down(int x) { if(lazy[x]) { swap(ch[x][0], ch[x][1]); lazy[ch[x][0]] ^= 1; lazy[ch[x][1]] ^= 1; lazy[x] = 0; }}void Rotate(int x) { int y = fa[x], z = fa[y]; push_down(y), push_down(x);///区间反转 int k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x);}void Splay(int x, int goal = 0) { push_down(x);///区间反转 while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}int Kth(int k) { int cur = rt; while(true) { push_down(cur); ///区间反转 if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; }}///区间反转void Reverse(int l, int r) { int x = Kth(l), y = Kth(r+2); Splay(x), Splay(y, x); lazy[ch[y][0]] ^= 1;}void Cut(int l, int r, int c) { int x = Kth(l), y = Kth(r+2); Splay(x), Splay(y, x); int cur = ch[y][0]; fa[cur] = 0; ch[y][0] = 0; x = Kth(c+1), y = Kth(c+2); Splay(x), Splay(y, x); fa[cur] = y; ch[y][0] = cur; Splay(cur);}void Output(int x) { push_down(x); if(ch[x][0]) Output(ch[x][0]); if(1 <= val[x] && val[x] <= n) printf("%d%c", val[x], " \n"[++tmp == n]); if(ch[x][1]) Output(ch[x][1]);}inline int NewNode(int x) { int cur = ++ncnt; ch[cur][0] = ch[cur][1] = fa[cur] = 0; val[cur] = x; sz[cur] = cnt[cur] = 1; lazy[cur] = 0; return cur;}int build(int l, int r, int *a) { if(l > r) return 0; int mid = l+r >> 1, cur = NewNode(a[mid]); if(l == r) return cur; if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur; if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur; push_up(cur); return cur;}int main() { for (int i = 0; i < N; ++i) a[i] = i; while(~scanf("%d %d", &n, &m)) { if(n == -1 && m == -1) break; rt = ncnt = ch[0][0] = ch[1][0] = fa[0] = sz[0] = cnt[0] = lazy[0] = 0; rt = build(0, n+1, a); for (int i = 1; i <= m; ++i) { scanf("%s", s); if(s[0] == 'C') { scanf("%d %d %d", &x, &y, &z); Cut(x, y, z); } else { scanf("%d %d", &x, &y); Reverse(x, y); } } tmp = 0; Output(rt); } return 0;}
            
           
          
         
        
       
      

 

思路：平衡树

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
            
             #define pli pair
             
              #define pii pair
              
               #define piii pair
               
                #define pdi pair
                
                 #define pdd pair
                 
                  #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 1e5 + 10;const int MOD = 1e6;struct splay { int ch[N][2], cnt[N], fa[N], sz[N], ncnt, rt; int n, m; LL val[N]; inline int ck(int x) { return ch[fa[x]][1] == x; } inline void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; } void Rotate(int x) { int y = fa[x], z = fa[y]; int k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x); } void Splay(int x, int goal = 0) { while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x; } void Find(LL x) { if(!rt) return ; int cur = rt; while(ch[cur][x>val[cur]] && x != val[cur]) cur = ch[cur][x>val[cur]]; Splay(cur); } void Insert(LL x) { int cur = rt, p = 0; while(cur && val[cur] != x) { p = cur; cur = ch[cur][x>val[cur]]; } if(cur) cnt[cur]++; else { cur = ++ncnt; if(p) ch[p][x>val[p]] = cur; fa[cur] = p; ch[cur][0] = ch[cur][1] = 0; val[cur] = x; cnt[cur] = sz[cur] = 1; } Splay(cur); } int Kth(int k) { int cur = rt; while(true) { if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; } } int Pre(LL x) { Find(x); if(val[rt] < x) return rt; int cur = ch[rt][0]; while(ch[cur][1]) cur = ch[cur][1]; return cur; } int Succ(LL x) { Find(x); if(val[rt] > x) return rt; int cur = ch[rt][1]; while(ch[cur][0]) cur = ch[cur][0]; return cur; } int pre(LL x) { Find(x); if(val[rt] <= x) return rt; int cur = ch[rt][0]; while(ch[cur][1]) cur = ch[cur][1]; return cur; } int succ(LL x) { Find(x); if(val[rt] >= x) return rt; int cur = ch[rt][1]; while(ch[cur][0]) cur = ch[cur][0]; return cur; } void Remove(LL x) { int last = Pre(x), next = Succ(x); Splay(last), Splay(next, last); int del = ch[next][0]; if(cnt[del] > 1) cnt[del]--, Splay(del); else ch[next][0] = 0, push_up(next), push_up(last); } inline int NewNode(LL x) { int cur = ++ncnt; ch[cur][0] = ch[cur][1] = fa[cur] = 0; val[cur] = x; sz[cur] = cnt[cur] = 1; return cur; } inline void init() { ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = sz[0] = cnt[0] = val[0] = 0; }}t1, t2;int T, a, b;int main() { scanf("%d", &T); t1.init(); t2.init(); t1.Insert(LONG_MIN); t1.Insert(LONG_MAX); t2.Insert(LONG_MIN); t2.Insert(LONG_MAX); LL ans = 0; while(T--) { scanf("%d %d", &a, &b); if(a == 0) { if(t2.sz[t2.rt] == 2) t1.Insert(b); else { LL del, tmp = LONG_MAX; LL pre = t2.val[t2.pre(b)]; if(pre != LONG_MIN && abs(pre - b) < tmp) { tmp = abs(pre-b); del = pre; } LL succ = t2.val[t2.succ(b)]; if(succ != LONG_MAX && abs(succ - b) < tmp) { tmp = abs(succ-b); del = succ; } (ans += tmp) %= MOD; t2.Remove(del); } } else { if(t1.sz[t1.rt] == 2) t2.Insert(b); else { LL del, tmp = LONG_MAX; LL pre = t1.val[t1.pre(b)]; if(pre != LONG_MIN && abs(pre - b) < tmp) { tmp = abs(pre-b); del = pre; } LL succ = t1.val[t1.succ(b)]; if(succ != LONG_MAX && abs(succ - b) < tmp) { tmp = abs(succ-b); del = succ; } (ans += tmp) %= MOD; t1.Remove(del); } } } printf("%lld\n", ans); return 0;}
                 
                
               
              
             
            
           
          
         
        
       
      

思路：常规操作，一开始数据范围看错，一直RE

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
             
              #define pli pair
              
               #define pii pair
               
                #define piii pair
                
                 #define pdi pair
                 
                  #define pdd pair
                  
                   #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 2.2e6;int ch[N][2], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;char val[N], s[100];string t;inline int ck(int x) { return ch[fa[x]][1] == x;}inline void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x];}///区间反转inline void push_down(int x) { if(lazy[x]) { swap(ch[x][0], ch[x][1]); lazy[ch[x][0]] ^= 1; lazy[ch[x][1]] ^= 1; lazy[x] = 0; }}void Rotate(int x) { int y = fa[x], z = fa[y]; push_down(y), push_down(x);///区间反转 int k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x);}void Splay(int x, int goal = 0) { push_down(x);///区间反转 while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}void Insert(char x) { int cur = rt, p = 0; while(cur && val[cur] != x) { p = cur; cur = ch[cur][x>val[cur]]; } if(cur) cnt[cur]++; else { cur = ++ncnt; if(p) ch[p][x>val[p]] = cur; fa[cur] = p; ch[cur][0] = ch[cur][1] = 0; val[cur] = x; cnt[cur] = sz[cur] = 1; } Splay(cur);}int Kth(int k) { int cur = rt; while(true) { push_down(cur); ///区间反转 if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; }}inline int NewNode(char x) { int cur = ++ncnt; ch[cur][0] = ch[cur][1] = fa[cur] = lazy[cur] = 0; val[cur] = x; sz[cur] = cnt[cur] = 1; return cur;}void Reverse(int l, int r) { int x = Kth(l), y = Kth(r+2); Splay(x), Splay(y, x); lazy[ch[y][0]] ^= 1;}void Delete(int l, int r) { int x = Kth(l), y = Kth(r+2); Splay(x), Splay(y, x); ch[y][0] = 0; push_up(y), push_up(x);}int build(int l, int r, string &a) { if(l > r) return 0; int mid = l+r >> 1, cur = NewNode(a[mid]); if(l == r) return cur; if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur; if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur; push_up(cur); return cur;}void Insert(int x, int n) { int u = Kth(x), v = Kth(x+1); Splay(u), Splay(v, u); int cur = build(0, n-1, t); fa[cur] = v; ch[v][0] = cur; push_up(v), push_up(u); Splay(cur);}inline void init() { ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = sz[0] = cnt[0] = lazy[0] = 0;}int T, n, k, a, b, now = 0;int main() { init(); Insert('#'); Insert('*'); cin >> T; for (int i = 0; i < T; ++i) { cin >> s; if(s[0] == 'M') { cin >> k; now = k; } else if(s[0] == 'I') { cin >> n; cin.ignore(); getline(cin, t); Insert(now+1, n); } else if(s[0] == 'D') { cin >> n; Delete(now+1, now+n); } else if(s[0] == 'R') { cin >> n; Reverse(now+1, now+n); } else if(s[0] == 'G') { char t = val[Kth(now+2)]; if(t != '\n') putchar(t); putchar('\n'); } else if(s[0] == 'P') --now; else if(s[0] == 'N') ++now; } return 0;}
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

思路：常规操作，REVOLVE记得取模，这个很坑

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
             
              #define pli pair
              
               #define pii pair
               
                #define piii pair
                
                 #define pdi pair
                 
                  #define pdd pair
                  
                   #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 2e5 + 10;int ch[N][2], cnt[N], fa[N], sz[N], lazy[N], ncnt = 0, rt = 0;LL val[N], a[N], tree[N], add[N];inline int ck(int x) { return ch[fa[x]][1] == x;}inline void push_up(int x) { int l = ch[x][0], r = ch[x][1]; tree[x] = min(val[x], min(tree[l], tree[r])); sz[x] = sz[l] + sz[r] + cnt[x];}///区间反转inline void push_down(int x) { int l = ch[x][0], r = ch[x][1]; if(lazy[x]) { swap(ch[x][0], ch[x][1]); if(l) lazy[l] ^= 1; if(r) lazy[r] ^= 1; lazy[x] = 0; } if(add[x]) { if(l) val[l] += add[x], tree[l] += add[x], add[l] += add[x]; if(r) val[r] += add[x], tree[r] += add[x], add[r] += add[x]; add[x] = 0; }}void Rotate(int x) { int y = fa[x], z = fa[y]; push_down(y), push_down(x);///区间反转 int k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x);}void Splay(int x, int goal = 0) { push_down(x);///区间反转 while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}int Kth(int k) { int cur = rt; while(true) { push_down(cur); ///区间反转 if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; }}inline int NewNode(LL x) { int cur = ++ncnt; ch[cur][0] = ch[cur][1] = fa[cur] = add[cur] = lazy[cur] = 0; val[cur] = x; tree[cur] = x; sz[cur] = cnt[cur] = 1; return cur;}///区间反转void REVERSE(int l, int r) { int x = Kth(l), y = Kth(r+2); Splay(x), Splay(y, x); int cur = ch[y][0]; lazy[cur] ^= 1;}void ADD(int l, int r, LL z) { int x = Kth(l), y = Kth(r+2); Splay(x), Splay(y, x); val[ch[y][0]] += z; tree[ch[y][0]] += z; add[ch[y][0]] += z; push_up(y), push_up(x);}void REVOLVE(int l, int r, int z) { int len = r-l+1; z = (z%len + len) % len; if(!z) return ; int ll = r-z+1, rr = r; int x = Kth(ll), y = Kth(rr+2); Splay(x), Splay(y, x); int cur = ch[y][0]; ch[y][0] = 0; push_up(y), push_up(x); x = Kth(l), y = Kth(l+1); Splay(x), Splay(y, x); ch[y][0] = cur; fa[cur] = y; push_up(y), push_up(x); Splay(cur);}LL MIN(int l, int r) { int x = Kth(l), y = Kth(r+2); Splay(x), Splay(y, x); return tree[ch[y][0]];}void INSERT(int x, LL y) { int u = Kth(x+1), v = Kth(x+2); Splay(u), Splay(v, u); int cur = NewNode(y); fa[cur] = v; ch[v][0] = cur; push_up(v), push_up(u);}void DELETE(int x) { int u = Kth(x), v = Kth(x+2); Splay(u), Splay(v, u); ch[v][0] = 0; push_up(v), push_up(u);}int build(int l, int r, LL *a) { if(l > r) return 0; int mid = l+r >> 1, cur = NewNode(a[mid]); if(l == r) return cur; if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur; if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur; push_up(cur); return cur;}inline void init() { ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = sz[0] = cnt[0] = val[0] = add[0] = lazy[0] = 0; tree[0] = LONG_MAX;}int n, m, x, y;LL z;char s[100];int main() { init(); scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]); a[0] = a[n+1] = LONG_MAX; rt = build(0, n+1, a); scanf("%d", &m); for (int i = 1; i <= m; ++i) { scanf("%s", s); if(s[0] == 'A') { scanf("%d %d %lld", &x, &y, &z); ADD(x, y, z); } else if(s[0] == 'R' && s[3] == 'E') { scanf("%d %d", &x, &y); REVERSE(x, y); } else if(s[0] == 'R' && s[3] == 'O') { scanf("%d %d %lld", &x, &y, &z); REVOLVE(x, y, z); } else if(s[0] == 'I') { scanf("%d %d", &x, &y); INSERT(x, y); } else if(s[0] == 'D') { scanf("%d", &x); DELETE(x); } else if(s[0] == 'M') { scanf("%d %d", &x, &y); printf("%lld\n", MIN(x, y)); } } return 0;}
                  
                 
                
               
              
             
            
           
          
         
        
       
      

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define LL long longconst int N = 1e5 + 10;int ch[N][2], cnt[N], fa[N], sz[N], ncnt = 0, rt = 0;LL add[N], tree[N], val[N], a[N];inline int ck(int x) { return ch[fa[x]][1] == x;}inline void push_up(int x) { sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + cnt[x]; tree[x] = val[x] + tree[ch[x][0]] + tree[ch[x][1]];}///区间反转inline void push_down(int x) { if(add[x]) { int l = ch[x][0], r = ch[x][1]; if(l) add[l] += add[x], val[l] += add[x], tree[l] += sz[l]*1LL*add[x]; if(r) add[r] += add[x], val[r] += add[x], tree[r] += sz[r]*1LL*add[x]; add[x] = 0; }}void Rotate(int x) { int y = fa[x], z = fa[y]; push_down(y), push_down(x);///区间反转 int k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x; push_up(y), push_up(x);}void Splay(int x, int goal = 0) { push_down(x);///区间反转 while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}int Kth(int k) { int cur = rt; while(true) { push_down(cur); ///区间反转 if(ch[cur][0] && k <= sz[ch[cur][0]]) cur = ch[cur][0]; else if(k > sz[ch[cur][0]] + cnt[cur]) k -=sz[ch[cur][0]] + cnt[cur], cur = ch[cur][1]; else return cur; }}void ADD(int l, int r, LL c) { int x = Kth(l), y = Kth(r+2); Splay(x), Splay(y, x); add[ch[y][0]] += c; tree[ch[y][0]] += sz[ch[y][0]]*1LL*c; val[ch[y][0]] += c; push_up(y), push_up(x);}LL SUM(int l, int r) { int x = Kth(l), y = Kth(r+2); Splay(x), Splay(y, x); return tree[ch[y][0]];}inline int NewNode(LL x) { int cur;cur = ++ncnt; ch[cur][0] = ch[cur][1] = fa[cur] = add[cur] = 0; val[cur] = x; tree[cur] = x; sz[cur] = cnt[cur] = 1; return cur;}int build(int l, int r, LL *a) { if(l > r) return 0; int mid = l+r >> 1, cur = NewNode(a[mid]); if(l == r) return cur; if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur; if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur; push_up(cur); return cur;}inline void init() { ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = sz[0] = cnt[0] = val[0] = add[0] = tree[0] = 0;}int n, m, l, r;LL c;char s[100];int main() { init(); scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%lld", &a[i]); rt = build(0, n+1, a); for (int i = 1; i <= m; ++i) { scanf("%s", s); if(s[0] == 'Q') { scanf("%d %d", &l, &r); printf("%lld\n", SUM(l, r)); } else if(s[0] == 'C') { scanf("%d %d %lld", &l, &r, &c); ADD(l, r, c); } } return 0;}
           
          
         
        
       
      

 

将树按入时间戳和出时间戳变成线性结构，然后在这个线性结构上用splay维护

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdi pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 1e5 + 100;int ch[N][2], val[N], cnt[N], fa[N], sz[N], ncnt = 0, rt = 0;int n, m, a, now = 0;vector
             
               g[N];int L[N], R[N], dfn[N], x, y;char s[100];inline int ck(int x) { return ch[fa[x]][1] == x;}void Rotate(int x) { int y = fa[x], z = fa[y]; int k = ck(x), w = ch[x][k^1]; ch[y][k] = w, fa[w] = y; ch[z][ck(y)] = x, fa[x] = z; ch[x][k^1] = y, fa[y] = x;}void Splay(int x, int goal = 0) { while(fa[x] != goal) { int y = fa[x], z = fa[y]; if(z != goal) { if(ck(x) == ck(y)) Rotate(y); else Rotate(x); } Rotate(x); } if(!goal) rt = x;}inline int NewNode(int x) { int cur = ++ncnt; ch[cur][0] = ch[cur][1] = fa[cur] = 0; val[cur] = abs(x); if(x > 0) L[x] = cur; else R[-x] = cur; return cur;}int build(int l, int r, int *a) { if(l > r) return 0; int mid = l+r >> 1, cur = NewNode(a[mid]); if(l == r) return cur; if(ch[cur][0] = build(l, mid-1, a)) fa[ch[cur][0]] = cur; if(ch[cur][1] = build(mid+1, r, a)) fa[ch[cur][1]] = cur; return cur;}inline void init() { ncnt = rt = ch[0][0] = ch[0][1] = fa[0] = val[0] = 0;}void dfs(int u) { dfn[++now] = u; for (int v : g[u]) dfs(v); dfn[++now] = -u;}inline int get_min(int x) { while(x && ch[x][0]) x = ch[x][0]; return x;}inline int get_max(int x) { while(x && ch[x][1]) x = ch[x][1]; return x;}int QUERY(int x) { int u = L[x]; Splay(u); return get_min(u);}void MOVE(int X, int Y) { int u = L[X], v = R[X]; Splay(u), Splay(v, u); int x = ch[u][0], y = ch[v][1]; int xx = get_max(x); fa[x] = 0, ch[u][0] = 0; fa[y] = 0, ch[v][1] = 0; if(y && xx) ch[xx][1] = y, fa[y] = xx; if(Y == 0) return ; if(QUERY(Y) == u) { fa[x] = u, ch[u][0] = x; fa[y] = v, ch[v][1] = y; ch[xx][1] = 0; return ; } int uu = L[Y]; Splay(uu); int vv = get_min(ch[uu][1]); Splay(vv, uu); ch[vv][0] = u; fa[u] = vv;}int main() { bool f = false; while(~scanf("%d", &n)) { if(f) printf("\n"); else f = true; init(); for (int i = 1; i <= n; ++i) { scanf("%d", &a); g[a].pb(i); } for (int u : g[0]) { now = 0; dfs(u); build(1, now, dfn); } scanf("%d", &m); for (int i = 1; i <= m; ++i) { scanf("%s", s); if(s[0] == 'M') { scanf("%d %d", &x, &y); MOVE(x, y); } else if(s[0] == 'Q') { scanf("%d", &x); printf("%d\n", val[QUERY(x)]); } } for (int i = 0; i <= n; ++i) g[i].clear(); } return 0;}
             
            
           
          
         
        
       
      

 

易错点：

1.修改后记得push_up

2.一直往左子树或右子树走时记得第一步判当前节点是不是0

套板子一时爽，一直套一直爽

Link-Cut-Tree

模板：

const int N = 3e5 + 5;int f[N],v[N],s[N],r[N],hep[N],ch[N][2];inline int get(int x){    return ch[f[x]][0]==x||ch[f[x]][1]==x;}inline void pushup(int x){    s[x]=s[ch[x][1]]^s[ch[x][0]]^v[x];}inline void filp(int x){    swap(ch[x][0],ch[x][1]);r[x]^=1;}inline void pushdown(int x){    if(!r[x])return;r[x]=0;    if(ch[x][0])filp(ch[x][0]);    if(ch[x][1])filp(ch[x][1]);}inline void rotate(int x){    int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k];    if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v;    if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);}inline void Splay(int x){    int y=x,top=0;hep[++top]=y;    while(get(y))hep[++top]=y=f[y];    while(top)pushdown(hep[top--]);    while(get(x)){        y=f[x],top=f[y];        if(get(y))           rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y);        rotate(x);    }pushup(x);return;}inline void Access(int x){    for(register int y=0;x;x=f[y=x])       Splay(x),ch[x][1]=y,pushup(x);}inline void makeroot(int x){    Access(x);Splay(x);filp(x);}inline int findroot(int x){    Access(x);Splay(x);    while(ch[x][0])pushdown(x),x=ch[x][0];    return x;}inline void split(int x,int y){    makeroot(x);Access(y);Splay(y);}inline void link(int x,int y){    makeroot(x);if(findroot(y)!=x)f[x]=y;}inline void cut(int x,int y){    split(x,y);    if(findroot(y)==x&&f[x]==y&&!ch[x][1]){        f[x]=ch[y][0]=0;pushup(y);    }return;}

  

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdi pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 3e5 + 5;int f[N],v[N],s[N],r[N],hep[N],ch[N][2];inline int get(int x){ return ch[f[x]][0]==x||ch[f[x]][1]==x;}inline void pushup(int x){ s[x]=s[ch[x][1]]^s[ch[x][0]]^v[x];}inline void filp(int x){ swap(ch[x][0],ch[x][1]);r[x]^=1;}inline void pushdown(int x){ if(!r[x])return;r[x]=0; if(ch[x][0])filp(ch[x][0]); if(ch[x][1])filp(ch[x][1]);}inline void rotate(int x){ int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k]; if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v; if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);}inline void Splay(int x){ int y=x,top=0;hep[++top]=y; while(get(y))hep[++top]=y=f[y]; while(top)pushdown(hep[top--]); while(get(x)){ y=f[x],top=f[y]; if(get(y)) rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y); rotate(x); }pushup(x);return;}inline void Access(int x){ for(register int y=0;x;x=f[y=x]) Splay(x),ch[x][1]=y,pushup(x);}inline void makeroot(int x){ Access(x);Splay(x);filp(x);}inline int findroot(int x){ Access(x);Splay(x); while(ch[x][0])pushdown(x),x=ch[x][0]; return x;}inline void split(int x,int y){ makeroot(x);Access(y);Splay(y);}inline void link(int x,int y){ makeroot(x);if(findroot(y)!=x)f[x]=y;}inline void cut(int x,int y){ split(x,y); if(findroot(y)==x&&f[x]==y&&!ch[x][1]){ f[x]=ch[y][0]=0;pushup(y); }return;}int n, m, op, x, y;int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) scanf("%d", &v[i]); for (int i = 1; i <= m; ++i) { scanf("%d %d %d", &op, &x, &y); if(op == 0) split(x, y), printf("%d\n", s[y]); else if(op == 1) link(x, y); else if(op == 2) cut(x, y); else Splay(x), v[x] = y; } return 0;}
            
           
          
         
        
       
      

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdi pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 1e4 + 10;int f[N], r[N],hep[N],ch[N][2];inline int get(int x){ return ch[f[x]][0]==x||ch[f[x]][1]==x;}inline void pushup(int x){ return ;}inline void filp(int x){ swap(ch[x][0],ch[x][1]);r[x]^=1;}inline void pushdown(int x){ if(!r[x])return;r[x]=0; if(ch[x][0])filp(ch[x][0]); if(ch[x][1])filp(ch[x][1]);}inline void rotate(int x){ int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k]; if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v; if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);}inline void Splay(int x){ int y=x,top=0;hep[++top]=y; while(get(y))hep[++top]=y=f[y]; while(top)pushdown(hep[top--]); while(get(x)){ y=f[x],top=f[y]; if(get(y)) rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y); rotate(x); }pushup(x);return;}inline void Access(int x){ for(register int y=0;x;x=f[y=x]) Splay(x),ch[x][1]=y,pushup(x);}inline void makeroot(int x){ Access(x);Splay(x);filp(x);}inline int findroot(int x){ Access(x);Splay(x); while(ch[x][0])pushdown(x),x=ch[x][0]; return x;}inline void split(int x,int y){ makeroot(x);Access(y);Splay(y);}inline void link(int x,int y){ makeroot(x);if(findroot(y)!=x)f[x]=y;}inline void cut(int x,int y){ split(x,y); if(findroot(y)==x&&f[x]==y&&!ch[x][1]){ f[x]=ch[y][0]=0;pushup(y); }return;}char op[100];int n, m, u, v;int main() { scanf("%d", &n); scanf("%d", &m); for (int i = 1; i <= m; ++i) { scanf("%s %d %d", op, &u, &v); if(op[0] == 'C') link(u, v); else if(op[0] == 'D') cut(u, v); else { makeroot(u); if(findroot(v) != u) printf("No\n"); else printf("Yes\n"); } } return 0;}
            
           
          
         
        
       
      

思路：注意cut和普通的cut不一样

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdi pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 3e5 + 5;int f[N],v[N],mx[N],r[N],add[N], hep[N],ch[N][2];inline int get(int x){ return ch[f[x]][0]==x||ch[f[x]][1]==x;}inline void pushup(int x){ mx[x]= max(max(mx[ch[x][1]], mx[ch[x][0]]), v[x]);}inline void filp(int x){ swap(ch[x][0],ch[x][1]);r[x]^=1;}inline void pushdown(int x){ int ls = ch[x][0], rs = ch[x][1]; if(r[x]) { if(ls) filp(ls); if(rs) filp(rs); r[x] = 0; } if(add[x]) { if(ls) add[ls] += add[x], v[ls] += add[x], mx[ls] += add[x]; if(rs) add[rs] += add[x], v[rs] += add[x], mx[rs] += add[x]; add[x] = 0; }}inline void rotate(int x){ int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k]; if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v; if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);}inline void Splay(int x){ int y=x,top=0;hep[++top]=y; while(get(y))hep[++top]=y=f[y]; while(top)pushdown(hep[top--]); while(get(x)){ y=f[x],top=f[y]; if(get(y)) rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y); rotate(x); }pushup(x);return;}inline void Access(int x){ for(register int y=0;x;x=f[y=x]) Splay(x),ch[x][1]=y,pushup(x);}inline void makeroot(int x){ Access(x);Splay(x);filp(x);}inline int findroot(int x){ Access(x);Splay(x); while(ch[x][0])pushdown(x),x=ch[x][0]; return x;}inline void ADD(int x,int y, int w){ makeroot(x);Access(y);Splay(y); v[y] += w, add[y] += w, mx[y] += w;}inline void split(int x,int y){ makeroot(x);Access(y);Splay(y);}inline void link(int x,int y){ makeroot(x); if(findroot(y)!=x)f[x]=y;}inline void cut(int x,int y) { split(x,y); ch[y][0] = f[ch[y][0]] = 0;}int op, x, y, w, n, m;int U[N], V[N];int main() { while(~scanf("%d", &n)) { mx[0] = INT_MIN; for (int i = 1; i < n; ++i) scanf("%d %d", &U[i], &V[i]); for (int i = 1; i <= n; ++i) scanf("%d", &v[i]), mx[i] = v[i], add[i] = r[i] = ch[i][0] = ch[i][1] = f[i] = 0; for (int i = 1; i < n; ++i) link(U[i], V[i]); scanf("%d", &m); for (int i = 1; i <= m; ++i) { scanf("%d", &op); if(op == 1) { scanf("%d %d", &x, &y); if(findroot(x) == findroot(y)) printf("-1\n"); else link(x, y); } else if(op == 2){ scanf("%d %d", &x, &y); if(findroot(x) != findroot(y) || x == y) printf("-1\n"); else cut(x, y); } else if(op == 3) { scanf("%d %d %d", &w, &x, &y); if(findroot(x) != findroot(y)) printf("-1\n"); else ADD(x, y, w); } else { scanf("%d %d", &x, &y); if(findroot(x) != findroot(y)) printf("-1\n"); else split(x, y), printf("%d\n", mx[y]); } } printf("\n"); } return 0;}
            
           
          
         
        
       
      

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdi pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 1e5 + 5;int f[N],v[N],mx[N],r[N],hep[N],ch[N][2];inline int get(int x){ return ch[f[x]][0]==x||ch[f[x]][1]==x;}inline void pushup(int x){ mx[x] = max(max(mx[ch[x][0]], mx[ch[x][1]]), v[x]);}inline void filp(int x){ swap(ch[x][0],ch[x][1]);r[x]^=1;}inline void pushdown(int x){ if(!r[x])return;r[x]=0; if(ch[x][0])filp(ch[x][0]); if(ch[x][1])filp(ch[x][1]);}inline void Rotate(int x){ int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k]; if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v; if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);}inline void Splay(int x){ int y=x,top=0;hep[++top]=y; while(get(y))hep[++top]=y=f[y]; while(top)pushdown(hep[top--]); while(get(x)){ y=f[x],top=f[y]; if(get(y)) Rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y); Rotate(x); }pushup(x);return;}inline void Access(int x){ for(int y=0;x;x=f[y=x]) Splay(x),ch[x][1]=y,pushup(x);}inline void makeroot(int x){ Access(x);Splay(x);filp(x);}inline int findroot(int x){ Access(x);Splay(x); while(ch[x][0])pushdown(x),x=ch[x][0]; return x;}inline void split(int x,int y){ makeroot(x);Access(y);Splay(y);}inline void link(int x,int y){ makeroot(x);if(findroot(y)!=x)f[x]=y;}inline void cut(int x,int y){ split(x,y); if(findroot(y)==x&&f[x]==y&&!ch[x][1]){ f[x]=ch[y][0]=0;pushup(y); }return;}int n, m, x, y;char op[100];int main() { mx[0] = INT_MIN; scanf("%d", &n); for (int i = 1; i < n; ++i) scanf("%d%d", &x, &y), link(x, y); scanf("%d", &m); for (int i = 1; i <= m; ++i) { scanf("%s%d%d", op, &x, &y); if(op[0] == 'I') Splay(x), v[x] += y; else split(x, y), printf("%d\n", mx[y]); } return 0;}
            
           
          
         
        
       
      

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
      
       using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ULL unsigned LL#define pll pair
       
        #define pli pair
        
         #define pii pair
         
          #define piii pair
          
           #define pdi pair
           
            #define pdd pair
            
             #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 3e4 + 5;int f[N],s[N], v[N],r[N],hep[N],ch[N][2];inline int get(int x){ return ch[f[x]][0]==x||ch[f[x]][1]==x;}inline void pushup(int x){ s[x] = s[ch[x][0]] + s[ch[x][1]] + v[x];}inline void filp(int x){ swap(ch[x][0],ch[x][1]);r[x]^=1;}inline void pushdown(int x){ if(!r[x])return;r[x]=0; if(ch[x][0])filp(ch[x][0]); if(ch[x][1])filp(ch[x][1]);}inline void rotate(int x){ int y=f[x],z=f[y],k=ch[y][1]==x,v=ch[x][!k]; if(get(y))ch[z][ch[z][1]==y]=x;ch[x][!k]=y,ch[y][k]=v; if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);}inline void Splay(int x){ int y=x,top=0;hep[++top]=y; while(get(y))hep[++top]=y=f[y]; while(top)pushdown(hep[top--]); while(get(x)){ y=f[x],top=f[y]; if(get(y)) rotate((ch[y][0]==x)^(ch[top][0]==y)?x:y); rotate(x); }pushup(x);return;}inline void Access(int x){ for(register int y=0;x;x=f[y=x]) Splay(x),ch[x][1]=y,pushup(x);}inline void makeroot(int x){ Access(x);Splay(x);filp(x);}inline int findroot(int x){ Access(x);Splay(x); while(ch[x][0])pushdown(x),x=ch[x][0]; return x;}inline void split(int x,int y){ makeroot(x);Access(y);Splay(y);}inline bool link(int x,int y){ makeroot(x);if(findroot(y)!=x)f[x]=y; else return false; return true;}inline void cut(int x,int y){ split(x,y); if(findroot(y)==x&&f[x]==y&&!ch[x][1]){ f[x]=ch[y][0]=0;pushup(y); }return;}int n, m, x, y;char op[100];int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &v[i]); scanf("%d", &m); for (int i = 1; i <= m; ++i) { scanf("%s %d %d", op, &x, &y); if(op[0] == 'b') { if(link(x, y)) printf("yes\n"); else printf("no\n"); } else if(op[0] == 'p') { Splay(x); v[x] = y; } else { if(findroot(x) != findroot(y)) printf("impossible\n"); else split(x, y), printf("%d\n", s[y]); } } return 0;}