【bzoj1861】[Zjoi2006]Book 书架

2015.06.11 11:18 Thu | 19次阅读 | 旧日oi | 固定链接 | 源码

给定一个1-n的排列,每次可以把一个数放到任意一个位置,询问某个数上面有多少个数或者第x个数是什么。
按位置建一颗splay,记录每个数的编号,然后splay就随便搞搞就行了,之前要先加两个节点。
总刷水题代码能力都变弱了……

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 81000
#define key son[son[root][1]][0]
#define is(x) (son[fa[x]][1]==x)
#define inf 0x3f3f3f3f
int n,m,cnt,tot,root;
int a[N],pos[N];
int son[N][2],d[N],siz[N],val[N],fa[N];
void newnode(int &x,int v,int f)
{
    if(tot) x=d[tot--];
    else x=++cnt;
    fa[x]=f;val[x]=v;siz[x]=1;
    son[x][0]=son[x][1]=0;
}
void pushup(int x)
{
    siz[x]=siz[son[x][0]]+siz[son[x][1]]+1;
}
void build(int &x,int l,int r,int f)
{
    int mid=(l+r)>>1;
    newnode(x,a[mid],f);pos[a[mid]]=x;
    if(mid>l) build(son[x][0],l,mid-1,x);
    if(mid<r) build(son[x][1],mid+1,r,x);
    pushup(x);
}
void link(int x,int y,int d)
{
    fa[x]=y;son[y][d]=x;
}
void rotate(int x)
{
    int y=fa[x],z=fa[y],id=is(x),t=son[x][!id];
    link(x,z,is(y));link(y,x,!id);link(t,y,id);
    pushup(y);pushup(x);son[0][0]=son[0][1]=fa[0]=0;
}
void splay(int x,int g)
{
    while(fa[x]!=g)
    {
        int y=fa[x],z=fa[y];
        if(z==g)
        {
            rotate(x);
            break;
        }
        rotate(is(y)==is(x)?y:x);rotate(x);
    }
    if(!g) root=x;
}
int get_rank(int k)
{
    int x=root;
    while(x)
    {
        if(siz[son[x][0]]>=k) x=son[x][0];
        else if(siz[son[x][0]]+1==k) return x;
        else k-=siz[son[x][0]]+1,x=son[x][1];
    }
}
void del(int x)
{
    int k=siz[son[x][0]];
    splay(get_rank(k),0);
    splay(get_rank(k+2),root);
    key=0;pushup(son[root][1]);pushup(root);
}
void change(int x,int val)
{
    splay(x,0);
    int y=siz[son[x][0]];
    del(x);
    if(val==inf)
    {
        splay(get_rank(1),0);
        splay(get_rank(2),root);
        key=x;fa[x]=son[root][1];
        siz[x]=1;son[x][0]=son[x][1]=0;
        pushup(son[root][1]);pushup(root);
    }
    else if(val==-inf)
    {
        splay(get_rank(n),0);
        splay(get_rank(n+1),root);
        key=x;fa[x]=son[root][1];
        siz[x]=1;son[x][0]=son[x][1]=0;
        pushup(son[root][1]);pushup(root);
    }
    else
    {
        int k=y+val;
        int t1=get_rank(k),t2=get_rank(k+1);
        splay(t1,0);splay(t2,root);
        key=x;fa[x]=son[root][1];
        siz[x]=1;son[x][0]=son[x][1]=0;
        pushup(son[root][1]);pushup(root);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=2;i<=n+1;i++) scanf("%d",&a[i]);
    build(root,1,n+2,0);
    int x,y;char s[10];
    while(m--)
    {
        scanf("%s",s);
        if(s[0]=='T') scanf("%d",&x),change(pos[x],inf);
        else if(s[0]=='B') scanf("%d",&x),change(pos[x],-inf);
        else if(s[0]=='I') scanf("%d%d",&x,&y),change(pos[x],y);
        else if(s[0]=='A')
            scanf("%d",&x),splay(pos[x],0),printf("%d\n",siz[son[root][0]]-1);
        else scanf("%d",&x),printf("%d\n",val[get_rank(x+1)]);
    }
}```