Warning: session_start(): open(/tmp/sess_d24e16cf4de014f1986f1aeb99e6a9ef, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/4/43994124a9168f34c03db2ff7cd35d94.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 主席树 ======
===== 例题 =====
[[https://www.luogu.com.cn/problem/P3834|洛谷 P3834 【模板】可持久化线段树 2（主席树）]]
参考代码：
#include
using namespace std;
const int N=2e5+5;
int cnt;
int a[N],b[N],rt[N];
int tr[N<<5],ls[N<<5],rs[N<<5];
void build(int& o,int l,int r){
o=++cnt;
tr[o]=0;
int mid=l+r>>1;
if(l==r){
return;
}
build(ls[o],l,mid);
build(rs[o],mid+1,r);
}
void xg(int& o,int l,int r,int pre,int x){
o=++cnt;
ls[o]=ls[pre];
rs[o]=rs[pre];
tr[o]=tr[pre]+1;
int mid=l+r>>1;
if(l==r) return;
if(x<=mid) xg(ls[o],l,mid,ls[pre],x);
if(x>mid) xg(rs[o],mid+1,r,rs[pre],x);
}
int cx(int u,int v,int l,int r,int k){
if(l>=r) return l;
int x=tr[ls[v]]-tr[ls[u]];
int mid=l+r>>1;
if(x>=k) return cx(ls[u],ls[v],l,mid,k);
else return cx(rs[u],rs[v],mid+1,r,k-x);
}
int main(){
int n,q,m;
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
}
sort(b+1,b+n+1);
m=unique(b+1,b+n+1)-b-1;
build(rt[0],1,m);
for(int i=1;i<=n;i++){
int t=lower_bound(b+1,b+m+1,a[i])-b;
xg(rt[i],1,m,rt[i-1],t);
}
while(q--){
int x,y,z;
scanf("%d %d %d",&x,&y,&z);
int t=cx(rt[x-1],rt[y],1,m,z);
printf("%d\n",b[t]);
}
return 0;
}