就是给你一摞书,然后又询问第k大,编号为x的书是第几大,然后修改书的位置
splay模板题。。。然而我还是不会,,,又遇到lrj的书的坑了,rj的书里没有father,顿时弄得我ask不会搞了
注意合并和分离的时候考虑一下会不会出空树,如果是空树就会RE,特判一下
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; struct Node{ Node *ch[2]; Node *father; int s; int v; inline int cmp(int x){ int ret = 0; if(ch[0] != NULL) ret += ch[0] -> s; if(x <= ret) return 0; ret ++; if(ret == x) return -1; return 1; } inline void maintain(){ s = 1; if(ch[0] != NULL) s += ch[0] -> s; if(ch[1] != NULL) s += ch[1] -> s; return; } }; struct Splay{ Node ft[100000]; int size; Node *p; int num[100000]; int a[100000]; inline void init(){ size = 0; p -> ch[0] = p -> ch[1] = p -> father = NULL; return; } inline void rotate(Node* &o, int d){ Node* k = o -> ch[d ^ 1]; o -> ch[d ^ 1] = k -> ch[d]; k -> ch[d] = o; o -> maintain(); k -> maintain(); o = k; o -> father = o -> ch[d] -> father; if(o -> ch[d] -> ch[d ^ 1] != NULL) o -> ch[d] -> ch[d ^ 1] -> father = o -> ch[d]; o -> ch[d] -> father = o; return; } inline void insert(Node* &o, int l, int r){ if(r < l) return; int mid = (l + r) / 2; o = &ft[size]; size ++; o -> ch[0] = o -> ch[1] = o -> father = NULL; o -> v = a[mid]; num[o -> v] = size - 1; if(l != r){ insert(o -> ch[0], l, mid - 1); if(o -> ch[0] != NULL) o -> ch[0] -> father = o; insert(o -> ch[1], mid + 1, r); if(o -> ch[1] != NULL) o -> ch[1] -> father = o; } o -> maintain(); return; } inline void splay(Node* &o, int k){ int d = o -> cmp(k); if(d == 1 && o -> ch[0] != NULL) k = k - o -> ch[0] -> s - 1; else if(d == 1) k --; if(d != -1){ Node* w = o -> ch[d]; int d2 = w -> cmp(k); int k2 = k; if(d2 != 0 && w -> ch[0] != NULL) k2 = k2 - w -> ch[0] -> s - 1; else if(d2 != 0) k2 --; if(d2 != -1){ splay(w -> ch[d2], k2); if(d == d2) rotate(o, d ^ 1); else rotate(o -> ch[d], d); } rotate(o, d ^ 1); } return; } inline Node* merge(Node* left, Node* right){ if(left == NULL) return right; if(right == NULL) return left; splay(left, left -> s); left -> ch[1] = right; left -> ch[1] -> father = left; left -> maintain(); return left; } inline void split(Node* o, int k, Node* &left, Node* &right){ if(k == 0){ left = NULL; right = o; return; } splay(o, k); left = o; right = o -> ch[1]; if(right != NULL) right -> father = NULL; left -> ch[1] = NULL; left -> maintain(); return; } inline int rank(Node* &o, int k){ int d = o -> cmp(k); if(d == -1) return o -> v; int st = 0; if(o -> ch[0] != NULL) st = o -> ch[0] -> s; if(d == 1) k = k - st - 1; return rank(o -> ch[d], k); } inline int ask(int k){ int ret = 0; Node* o = &ft[num[k]]; if(o -> ch[0] != NULL) ret = o -> ch[0] -> s; while(o -> father != NULL){ if(o -> father -> ch[1] == o){ int u = 0; if(o -> father -> ch[0] != NULL) u = o -> father -> ch[0] -> s; ret += (u + 1); } o = o -> father; } return ret; } inline void Top(int k){ int t = ask(k) + 1; Node *left, *mid, *right; split(p, t, left, right); split(left, t - 1, left, mid); left = merge(mid, left); left = merge(left, right); p = left; return; } inline void Bottom(int k){ int t = ask(k) + 1; Node *left, *mid, *right; split(p, t, left, right); split(left, t - 1, left, mid); left = merge(left, right); left = merge(left, mid); p = left; return; } inline void Insert(int k, int w){ int t = ask(k) + 1; Node *left, *mid, *right; split(p, t, left, right); split(left, t - 1, left, mid); left = merge(left, right); split(left, t + w - 1, left, right); left = merge(left, mid); left = merge(left, right); p = left; return; } } wt; int main(){ int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i ++) scanf("%d", &wt.a[i]); wt.insert(wt.p, 1, n); char str[20]; for(int i = 1; i <= m; i ++){ scanf("%s", str); int k, w; if(str[0] == 'Q'){ scanf("%d", &k); printf("%d\n", wt.rank(wt.p, k)); } else if(str[0] == 'A'){ scanf("%d", &k); printf("%d\n", wt.ask(k)); } else if(str[0] == 'T'){ scanf("%d", &k); wt.Top(k); } else if(str[0] == 'B'){ scanf("%d", &k); wt.Bottom(k); } else{ scanf("%d%d", &k, &w); wt.Insert(k, w); } } return 0; }