bzoj1861 书架

题目链接

思路

用一个平衡树维护点的编号和权值。这里的权值是自己赋上去的。

操作1，就把x从平衡树中删掉，然后将其权值变为最小值，重新插入。

操作2，与操作1类似，只要将其权值变为最大值再重新插入就行了。

操作3，其实就是将x与他的前驱或者后继交换。也很容易实现。

操作4，查询排名。

操作5，查找第k大。

代码

/*
* @author: wxyww
* @date:   2019-05-25 10:50:13
* @last modified time: 2019-05-25 17:21:41
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
#define ls tr[cur].ch[0]
#define rs tr[cur].ch[1]
const  int n = 500000 + 100,inf = 1e9 + 10;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    int ch[2],val,id,key,siz;
}tr[n];
int tot;
int root,dy[n];
void up(int cur) {
    tr[cur].siz = tr[ls].siz + tr[rs].siz + 1;
}
void rotate(int &cur,int f) {
    int son = tr[cur].ch[f];
    tr[cur].ch[f] = tr[son].ch[f ^ 1];
    tr[son].ch[f ^ 1] = cur;
    up(cur);
    cur = son;
    up(cur);
}
void insert(int &cur,int val,int key) {
    if(!cur) {
        cur = ++tot;
        tr[cur].val = val;tr[cur].key = key;
        tr[cur].id = rand();tr[cur].siz = 1;
        dy[key] = cur;
        return;
    }
    tr[cur].siz++;
    int d = val > tr[cur].val;
    insert(tr[cur].ch[d],val,key);
    if(tr[tr[cur].ch[d]].id < tr[cur].id) rotate(cur,d);
}
void del(int &cur,int val) {
    if(!cur) return;
    if(val == tr[cur].val) {
        if(!ls || !rs) {cur = ls + rs;return;}
        
        int d = tr[rs].id < tr[ls].id;rotate(cur,d);
        del(cur,val);
    }
    else tr[cur].siz--,del(tr[cur].ch[val > tr[cur].val],val);
}
int rank(int cur,int val) {
    if(!cur) return 0;
    if(val == tr[cur].val) return tr[ls].siz;
    if(val < tr[cur].val) return rank(ls,val);
    else return rank(rs,val) + tr[ls].siz + 1;
}
int kth(int cur,int now) {
    while(1) {
        if(tr[ls].siz >= now) cur = ls;
        else if(tr[ls].siz + 1 == now) return tr[cur].key;
        else now -= tr[ls].siz + 1,cur = rs;
    }
}
int pred(int cur,int val) {
    if(!cur) {
        tr[++tot].val = -inf;
        return tot;
    }
    if(val <= tr[cur].val) return pred(ls,val);
    int k = pred(rs,val);
    return tr[k].val > tr[cur].val ? k : cur;
}
int nex(int cur,int val) {
    if(!cur) {
        tr[++tot].val = inf;
        return tot;
    }
    if(val >= tr[cur].val) return nex(rs,val);
    int k = nex(ls,val);
    return tr[k].val < tr[cur].val ? k : cur;
}
int ll,rr,a[n];
char s[10];
int main() {
    srand(time(0));
    int n = read(),m = read();
    for(int i = 1;i <= n;++i) {
        int x = read();
        a[x] = i,insert(root,++rr,x);
    }
    while(m--) {
        scanf("%s",s + 1);
        if(s[1] == 't') {
            int x = read();
            del(root,a[x]);
            a[x] = --ll;
            insert(root,ll,x);
        }
        else if(s[1] == 'b') {
            int x = read();
            del(root,a[x]);a[x] = ++rr;
            insert(root,rr,x);
        }
        else if(s[1] == 'i') {
            int x = read(),y = read();
            if(!y) continue;
            int tmp;
            if(y == -1) tmp = pred(root,a[x]);
            else tmp = nex(root,a[x]);
            int zz = tr[tmp].key;
            swap(tr[tmp].key,tr[dy[x]].key);
            // printf("!!%d %d\n",x,zz);
            swap(dy[x],dy[zz]);
            swap(a[x],a[zz]);
        }
        else if(s[1] == 'a') {
            int x = read();
            printf("%d\n",rank(root,a[x]));
        }
        else {
            int x = read();
            printf("%d\n",kth(root,x));
        }
    }
    return 0;
}