可持久化线段树

可持久化线段树

可持久化线段树就是对[1,n]的每一个i,都建一颗线段树，然后为了省空间就复制了一部分的树

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

const int N=2e5+5;
struct zxs{
	int l,r,sum,ed;
}q[N*18*4];
int n,m,a[N],b[N],c[N],cnt=0;
int rt[N];
int newnode(int id){
	q[++cnt]=q[id];
	return cnt;
}
int uppdate(int l,int r,int id,int x,int val){
	int idd=newnode(id);
	if(l==r){
		q[idd].ed=x;
		q[idd].sum++;
		return idd;
	}
	int mid=(l+r)>>1;
	if(val<=mid) q[idd].l=uppdate(l,mid,q[id].l,x,val);//
	else q[idd].r=uppdate(mid+1,r,q[id].r,x,val);//
	int ls=q[q[idd].l].sum,rs=q[q[idd].r].sum;
	q[idd].sum=ls+rs;
	return idd;
}
int query(int l,int r,int u,int v,int k){
	if(l==r){
		return q[v].ed;
	}
	int mid=(l+r)>>1;
	int vv=q[v].l,uu=q[u].l;
	int stmp=q[vv].sum-q[uu].sum;
	if(k<=stmp) return query(l,mid,q[u].l,q[v].l,k);
	else return query(mid+1,r,q[u].r,q[v].r,k-stmp);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	    b[i]=a[i];
	}
	sort(b+1,b+n+1);
	int nn=unique(b+1,b+n+1)-b-1;
	for(int i=1;i<=n;i++){
		c[i]=upper_bound(b+1,b+nn+1,a[i])-b-1;
	};
    for(int i=1;i<=n;i++)
    {
    	rt[i]=uppdate(1,nn,rt[i-1],i,c[i]);
    }
    for(int i=1;i<=m;i++){
    	int l,r,k;
    	scanf("%d%d%d",&l,&r,&k);
    	int tp=query(1,nn,rt[l-1],rt[r],k);
    	printf("%d\n",a[tp]);
    }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59