[SCOI2014]方伯伯的OJ——线段树/平衡树

· · 题解

水水水，noip2017列队弱化版？

简化版题意：写一种数据结构，查询第 k 大。

（当然原题没有这么简单）

不过平衡树或者动态开点线段树都是可以的。

然后用一个 map（或者哈希表）存一下每个编号在线段树的哪个位置，在用另一个存一下每个位置上是哪个编号就没了。

（换成 unordered_map之后反而更慢了

代码：权值线段树写法，代码很短

#include<bits/stdc++.h>
#define N 100005
#define M N*33 
#define mid ((l+r)>>1)
#define inf 100100005
using namespace std;

inline void rd(int &X){
    X=0;int w=0;char ch=0;
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while( isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    X=w?-X:X;
}

int L,R;
map<int,int> id,id2;
int n,m,rt,cnt,ans;
int sum[M],ls[M],rs[M];

void ins(int &p,int x,int l=-inf,int r=inf){
    if(!p) p=++cnt;sum[p]++;if(l==r) return ;
    x<=mid ? ins(ls[p],x,l,mid) : ins(rs[p],x,mid+1,r);
}
int ask(int p,int x,int l=-inf,int r=inf){
    if(!sum[p] or l==r) return 0;
    return x<=mid ? ask(ls[p],x,l,mid) : ask(rs[p],x,mid+1,r)+sum[ls[p]];
}
int find(int p,int k,int l=-inf,int r=inf){
    if(l==r) return l;int num=max(0,min(R,mid)-max(L,l)+1-sum[ls[p]]);
    return num>=k ? find(ls[p],k,l,mid) : find(rs[p],k-num,mid+1,r);
}
inline void work1(int x){
    int now=(id.find(x)==id.end() ? x : id[x]);
    ans=now-L+1-ask(rt,now); ins(rt,now); id[x]=--L;id2[L]=x;   
}
inline void work2(int x){
    int now=(id.find(x)==id.end() ? x : id[x]);
    ans=now-L+1-ask(rt,now); ins(rt,now); id[x]=++R;id2[R]=x;
}
inline void change(int x,int y){
    int now=(id.find(x)==id.end() ? x : id[x]);
    ans=now-L+1-ask(rt,now); id[y]=now; id2[now]=y;
}
inline void ask(int x){
    ans=find(rt,x);ans=(id2.find(ans)==id2.end() ? ans : id2[ans]);
}
signed main(){
    rd(n);rd(m);L=1,R=n;
    while(m--){
        int pd,x,y;rd(pd);rd(x);
        if(pd==1) rd(y),change(x-ans,y-ans),printf("%d\n",ans);
        if(pd==2) work1(x-ans),printf("%d\n",ans);
        if(pd==3) work2(x-ans),printf("%d\n",ans);
        if(pd==4) ask(x-ans),printf("%d\n",ans);
    }
}