题解 P3285 【[SCOI2014]方伯伯的OJ】

· · 题解

考虑将所有用户分成3类

原本的1->n，被提前的，被拉后的

对2,3类都开个平衡树

记录每个用户属于哪一类，以及对应的平衡树中的节点编号

平衡树也反过来记录节点对应的用户编号

这样如果在2,3类查询rank,k大就ok了

如果在1类查询rank,k大

因为节点个数是O(n)的，所以不能直接维护

所以对不在1类的点用平衡树维护

O(mlogm)

在实现中，2,3类我直接用线段树维护了

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=l;i<=r;++i)
int lastans;
#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'0'); 
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}
int r()
{
#ifdef ONLINE_JUDGE
    return read()-lastans;
#else
    return read();
#endif
}

const int N=1e5+5;
int n,m,d;
struct SET
{
int a[N*3],id[N],n;
int insert(int _id)
{
    ++n;
    id[n]=_id;
    int i=n+d;
    a[i]=1;
    while(i>>=1)++a[i];
    return n;
}
void del(int i)
{
    i+=d;
    a[i]=0;
    while(i>>=1)--a[i];
}
int rank(int i)
{
    i+=d;
    int ans=a[i];
    while(i)
    {
        if(i&1)ans+=a[i-1];
        i>>=1;
    }
    return ans;
}
int find_by_rank(int x)
{
    int i=1;
    while(i<=d)
    {
        if(x<=a[i*2])i*=2;
        else 
        {
            x-=a[i*2];i=i*2+1;
        }
    }
    return id[i-d];    
}
};
SET pre,suf;

struct SPLAY
{
#define cl(x) c[x][0]
#define cr(x) c[x][1]
int fa[N],c[N][2],sz[N];
int v[N],n,rt;
int rank(int x)
{
    int ans=x;
    int i=rt;
    while(i)
    if(v[i]>x)i=cl(i);
    else 
    {
        ans-=sz[cl(i)]+1;
        i=cr(i);
    }
    return ans;
}
void sc(int y,int x,bool d)
{
    fa[x]=y;c[y][d]=x;
}
bool get(int x)
{
    return x==c[fa[x]][1];
}
void up(int x)
{
    sz[x]=sz[cl(x)]+sz[cr(x)]+1;
}
void rot(int x)
{
    int y=fa[x];bool d=get(x);
    if(y==rt)fa[rt=x]=0;
    else sc(fa[y],x,get(y));
    sc(y,c[x][!d],d);
    sc(x,y,!d);
    up(y);
}
void splay(int x,int to=0)
{
    int y;
    while(y=fa[x],y!=to)
    {
        if(fa[y]==to){rot(x);break;}
        rot(get(x)==get(y)?y:x);rot(x);
    }
    up(x);
}
void insert(int x)
{
    ++n;
    v[n]=x;sz[n]=1;
    if(!rt)
    {
        rt=n;return ;
    }
    int i=rt;
    while(1)
    {
        bool d=v[i]<x;
        if(c[i][d]) i=c[i][d];
        else 
        {
            sc(i,n,d);
            splay(n);
            return ;
        }
    }
}
map<int,int>dy;
int DY(int x)
{
    if(!dy.count(x))return x;
    return dy[x];
}
int find_by_rank(int x)
{
    if(!rt)return DY(x);
    int i=rt,i0=0,rk=1;
    while(i)
    {
        i0=i;
        if(x>v[i]-(sz[cl(i)]+rk)) 
        {
            rk+=sz[cl(i)]+1;
            i=c[i][1];
        }
        else i=c[i][0];
    }
    splay(i0);
    return DY(x+rk-1);
}
}out;

const int PRE=1,SUF=2;
struct point
{
    int in,id;
};
map<int,point>belong;//i de wei zhi  
point &B(int x)
{
    if(!belong.count(x))belong[x]=(point){0,x};
    return belong[x];
}
int rk(int x)
{
    if(B(x).in==1)
    {
        return pre.a[1]+1 - pre.rank(B(x).id);
    }
    if(B(x).in==2)
    {
        return n-suf.a[1]+suf.rank(B(x).id);
    }
    return pre.a[1]+out.rank(B(x).id);
}
int find_by_rank(int x)
{
    if(x<=pre.a[1]) return pre.find_by_rank(pre.a[1]-x+1);
    if(x>n-suf.a[1]) return suf.find_by_rank(x-(n-suf.a[1]));
    return out.find_by_rank(x-pre.a[1]);
}

int main()
{
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    n=read();m=read();
    for(d=1;d<m;d<<=1);d-=1;
    lastans=0;
    while(m--)
    {
        int type=read(),x=r(),ans;
        if(type==4)
        {
            ans=find_by_rank(x);
        }
        else 
        {
            ans=rk(x);
            if(type==1)
            {
                int y=r();
                B(y)=B(x);
                if(B(x).in) (B(x).in==PRE?pre:suf).id[B(x).id]=y;    
                else out.dy[B(x).id]=y;
            }
            else
            {
                if(B(x).in==0) out.insert(B(x).id);
                else 
                (B(x).in==PRE?pre:suf).del(B(x).id);    
                if(type==2) B(x)=(point){PRE,pre.insert(x)};
                else B(x)=(point){SUF,suf.insert(x)};
            }
        }

        printf("%d\n",lastans=ans);
    }
}