【jzoj5333】【NOIP2017提高A组模拟8.23】【大新闻】【可持久化线段树】

description

solution

可以发现把序列倒过来就是在队末加或删数维护前缀权值线段树即可， 这不就是主席树，直接做就可以了。

code

#include<set>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int const mn=2*1e5+9,mp=4*1e5+9,ma=1e9,inf=1e9+7;
int n,m,pon,a[mn],size[mp*31],son[mp*31][2];
void oper(int p,int q,int l,int r,int v){
int mid=(l+r)/2;
if(l==r){
        size[p]=size[q]+1;
return;
    }
if(v<=mid){
        son[p][1]=son[q][1];
        oper(son[p][0]=++pon,son[q][0],l,mid,v);
    }else{
        son[p][0]=son[q][0];
        oper(son[p][1]=++pon,son[q][1],mid+1,r,v);
    }
    size[p]=size[son[p][0]]+size[son[p][1]];
}
int qury(int p,int q,int l,int r,int v){
int mid=(l+r)/2,tmp;
if(l==r)return l;
if((tmp=size[son[p][0]]-size[son[q][0]])>=v)
return qury(son[p][0],son[q][0],l,mid,v);
else return qury(son[p][1],son[q][1],mid+1,r,v-tmp);
}
int main(){
    freopen("news.in","r",stdin);
    freopen("news.out","w",stdout);
    scanf("%d%d",&n,&m);
    fo(i,1,n)scanf("%d",&a[i]);
    pon=n+m;
    fd(i,n,1)oper(n-i+1,n-i,1,ma,a[i]);
int cnt=n;
    fo(cas,1,m){
int op;
        scanf("%d",&op);
if(op==1)cnt--;
else if(op==2){
int x;
            scanf("%d",&x);
            cnt++;
            oper(cnt,cnt-1,1,ma,x);
        }else{
int l,r,K;
            scanf("%d%d%d",&l,&r,&K);
printf("%d\n",qury(cnt-l+1,cnt-r,1,ma,K));
        }
    }
return 0;
}