欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

bzoj1861 书架

程序员文章站 2022-04-08 23:08:55
题目链接 思路 用一个平衡树维护点的编号和权值。这里的权值是自己赋上去的。 操作1,就把x从平衡树中删掉,然后将其权值变为最小值,重新插入。 操作2,与操作1类似,只要将其权值变为最大值再重新插入就行了。 操作3,其实就是将x与他的前驱或者后继交换。也很容易实现。 操作4,查询排名。 操作5,查找第 ......

题目链接

思路

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

操作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;
}