JZOJ 5933. 【NOIP2018模拟10.27】百鸽笼
题目
鸽鸽鸽
有一个序列,有3种操作。
①删除最左边的元素
②在序列的最左边加入一个数。
③查询序列中第l个数到第r个数中第k小的数。
题解
想到之前ifk通过动态树最终状态的dfs序将问题转化成静态树问题,我打算也用类似的方法。
其实不需要。
每次删除和插入的都是最左边的。难道不能将序列颠倒一下吗?
模板题。
心得
主席树不需要删除元素,只需要选择正确的rt[i],在rt[i]的基础上加元素即可。
PS:将相同大小的数组放在代码的同一行!!!不然很容易开小数组
每次开数组的时候留个心眼
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 200010
#define M 400010
#define P(a) putchar(a)
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
struct note{
int ls,rs,sum;
}tr[M*20];
struct noq{
int l,r,k,op;
}qu[N];
int gs,rt[M];
int i,j,k,l,n,m,opx,d2,top,ans;
int nl,nr;
int o[M],a[M],t2,cx;
int c[N];
int read(){
int fh=0,rs=0;char ch=0;
while((ch<'0')||(ch>'9')&&(ch^'-'))ch=getchar();
if(ch=='-')fh=1,ch=getchar();
while(ch>='0'&&ch<='9')rs=(rs<<3)+(rs<<1)+(ch^'0'),ch=getchar();
return fh?-rs:rs;
}
void write(int x){
if(x>9)write(x/10);
P(x%10+'0');
}
void change(int &px,int py,int l,int r){
px=++gs;
tr[px]=tr[py];
tr[px].sum++;
if(l==r)return;
int wz=(l+r)>>1;
if(opx<=wz)change(tr[px].ls,tr[py].ls,l,wz);
else change(tr[px].rs,tr[py].rs,wz+1,r);
}
int query(int px,int py,int l,int r,int k){
if(l==r)return a[l];
int wz=(l+r)>>1,x=tr[tr[px].ls].sum-tr[tr[py].ls].sum;
if(x<k)return query(tr[px].rs,tr[py].rs,wz+1,r,k-x);
else return query(tr[px].ls,tr[py].ls,l,wz,k);
}
int main(){
n=read();m=read();
fo(i,1,n){
c[i]=read();
a[++t2]=c[i];
}
fo(i,1,m){
qu[i].op=read();
if(qu[i].op==2){
qu[i].k=read();
a[++t2]=qu[i].k;
}
if(qu[i].op==3){
qu[i].l=read(),qu[i].r=read(),qu[i].k=read();
}
}
sort(a+1,a+t2+1);
cx=unique(a+1,a+t2+1)-a-1;
fo(i,1,n)c[i]=lower_bound(a+1,a+cx+1,c[i])-a;
fo(i,1,m)if(qu[i].op==2)qu[i].k=lower_bound(a+1,a+cx+1,qu[i].k)-a;
fd(i,n,1){
opx=c[i];
change(rt[i],rt[i+1],1,cx);
o[++top]=i;
}
d2=n;
fo(i,1,m){
if(qu[i].op==1){
top--;
}else
if(qu[i].op==2){
o[++top]=++d2;
opx=qu[i].k;
change(rt[d2],rt[o[top-1]],1,cx);
}else{
nl=o[top-qu[i].r];
nr=o[top-qu[i].l+1];
ans=query(rt[nr],rt[nl],1,cx,qu[i].k);
write(ans);
P('\n');
}
}
return 0;
}