Problem

第一行有两个数 n，m，分别表示书的个数以及命令的条数；第二行为 n 个正整数：第 i 个数表示初始时从上至下第 i 个位置放置的书的编号；第三行到 m + 2 行，每行一条命令。命令有 5 种形式：
1． Top S——表示把编号为 S 的书房在最上面。
2． Bottom S——表示把编号为 S 的书房在最下面。
3． Insert S T——T∈{-1，0，1}，若编号为 S 的书上面有 X 本书，则这条命令表示把这本书放回去后它的上面有 X + T 本书；
4． Ask S——询问编号为 S 的书的上面目前有多少本书。
5． Query S——询问从上面数起的第 S 本书的编号。

Solution

一道 Splay 的入门题，据说。
我还专门为了这个去打了父指针维护版。
这种询问序列具体内容的大概都得打父指针维护版。

啊，关于置顶我用了个比较蠢的方法。首先把东西旋上来，然后合并左右子树。
然后左右子树最小旋上来，点插到右子树。
实际上只用把东西旋上来，然后左子树与其后继合并即可。也就是直接右子树最小旋上来，接左子树。
啊我真 tm 蠢。

以及这个题又再次告诉我们了指针清零的重要性。

Code

#include<bits/stdc++.h>
#define DEBUG dfs(root), cout<<endl
using namespace std;

struct Node *nil;
struct Node {
    int v,s,c;
    Node *ch[2],*f;
    Node (int v=0):v(v),s(1),c(1) { ch[0]=ch[1]=f=nil; }
    int dir() {
        if(f==nil) return -1;
        return f->ch[1]==this;
    }
    void upd() { s=c+ch[0]->s+ch[1]->s; }
} *root, *pos[80010];
#define INF (0x7fffffff)
void init() {
    nil=new Node(-INF);
    root=nil->ch[0]=nil->ch[1]=nil->f=nil;
    nil->s=nil->c=0;
}
void dfs(Node *x) {
    if(x==nil) return;
    dfs(x->ch[0]), cout<<x->v<<' ', dfs(x->ch[1]);
}

void rot(Node *x) {
    Node *y=x->f;
    int d=x->dir();
    y->ch[d]=x->ch[!d];
    if(x->ch[!d]!=nil) x->ch[!d]->f=y;

    x->f=y->f;
    if(y->f!=nil) y->f->ch[y->dir()]=x;

    x->ch[!d]=y, y->f=x;
    if(y==root) root=x;
    y->upd();
}

void splay(Node *f, Node *x) {
    while(x->f!=f) {
        Node *y=x->f, *z=y->f;
        if(z==f) rot(x);
        else if(x->dir()==y->dir()) rot(y), rot(x);
        else rot(x), rot(x);
    }
    x->upd();
}

Node* kth(Node *x, int k) {
    int ss=x->ch[0]->s;
    if(k<=ss) return kth(x->ch[0], k);
    else if(k<=ss+x->c) return x;
    else return kth(x->ch[1], k-ss-x->c);
}

void swp(Node *x, Node *y) {
    Node *&a=pos[x->v], *&b=pos[y->v];
    swap(x->v, y->v);
    swap(a,b);
}

void merge(Node *&x1, Node *&x2) {
    if(x1==nil) swap(x1,x2);
    splay(x1->f, kth(x1,x1->s));
    x1->ch[1]=x2, x2->f=x1, x1->upd();
    if(x2==nil) x2->f=nil;
    x2=nil;
}

void top(int x) {
    splay(nil, pos[x]);
    Node *nd=root;
    root=root->ch[0], root->f=nd->ch[1]->f=nil;
    merge(root, nd->ch[1]);
    nd->ch[0]=nd->ch[1]=nil;
    splay(nil, kth(root,1));
    root->ch[0]=nd, nd->f=root, nd->upd(), root->upd();
}

int n,m;
void bot(int x) {
    splay(nil, pos[x]);
    Node *nd=root;
    root=root->ch[0], root->f=nd->ch[1]->f=nil;
    merge(root, nd->ch[1]);
    nd->ch[0]=nd->ch[1]=nil;
    splay(nil, kth(root,n-1));
    root->ch[1]=nd, nd->f=root, nd->upd(), root->upd();
}

void ins(int x, int t) {
    if(!t) return;
    splay(nil, pos[x]);
    if(t==-1) {
        splay(root, kth(root->ch[0],root->ch[0]->s));
        if(root->ch[0]!=nil) swp(root->ch[0], root);
    }
    else {
        splay(root, kth(root->ch[1],1));
        if(root->ch[1]!=nil) swp(root->ch[1], root);
    }
}

int rank(int x) {
    splay(nil, pos[x]);
    return root->ch[0]->s;
}

int main() {
    ios::sync_with_stdio(false);
    init();
    cin>>n>>m;
    int na;
    cin>>na;
    pos[na]=root=new Node(na);
    Node *nd=root;
    for(int i=2;i<=n;i++) cin>>na, nd->ch[1]=new Node(na), nd->ch[1]->f=nd, nd=nd->ch[1], pos[na]=nd;
    splay(root, nd);
    string opt;
    int nb;
    while(m--) {
        cin>>opt>>na;
        if(opt[0]=='T') top(na);
        else if(opt[0]=='B') bot(na);
        else if(opt[0]=='I') cin>>nb, ins(na,nb);
        else if(opt[0]=='A') cout<<rank(na)<<endl;
        else cout<<kth(root, na)->v<<endl;
    }
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol_luogu_2596.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆