BZOJ1861—

就是给你一摞书，然后又询问第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;
}
巴特西

BZOJ1861——book

最新文章

热门文章
