欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P3834 【模板】可持久化线段树 1(主席树) (多次查询第k大或第k小)

程序员文章站 2024-03-04 12:26:41
...

P3834 【模板】可持久化线段树 1(主席树)

 

 

#include <bits/stdc++.h>
using namespace std;
const int maxn = 300000;
int sum[maxn*20+5];//sum为森林的不同根结点
struct E{
	int num;
	int l,r;
}t[maxn*20+5];//t为tree树 
int n,sz,m,a[maxn],b[maxn],cnt;
int q; 
int build(int l,int r){
	int now = ++cnt;
	int mid = (l+r)>>1;
	if(l<r){
		t[now].l = build(l,mid);
		t[now].r = build(mid+1,r);
	}
	return now;
}
int update(int l,int r,int last,int p){
	int now = ++cnt;
	t[now].num = t[last].num+1;
	t[now].l = t[last].l;
	t[now].r = t[last].r;
	int mid = (l + r)>>1;
	if(l<r){
	if(p<=mid)t[now].l = update(l,mid,t[last].l,p);
	else t[now].r = update(mid+1,r,t[last].r,p);
	}
	return now;
}
int query(int u,int v,int l,int r,int k){
	if(l==r)return l;
	// v 左孩子包含点个数减去 u 左孩子包含点的个数 
	int tmp = t[t[v].l].num - t[t[u].l].num;
	int mid = (l+r)>>1;
	if(k<=tmp)return query(t[u].l,t[v].l,l,mid,k);
	else return query(t[u].r,t[v].r,mid+1,r,k - tmp);
}
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);
	sz = unique(b+1,b+n+1) - (b+1);
	cnt = 0;
	sum[0] = build(1,sz);//建立空树 
	for(int i=1;i<=n;i++) a[i] = lower_bound(b+1,b+sz+1,a[i]) - b;
	for(int i=1;i<=n;i++) sum[i] = update(1,sz,sum[i-1],a[i]);
	while(m--){
		int u,v,k;
		scanf("%d %d %d",&u,&v,&k);
		// [u,v]等价于 sum[v] - sum[u-1] 
		int ans = query(sum[u-1],sum[v],1,sz,k);
		printf("%d\n",b[ans]);
	}
	return 0;
}