“洛谷 P3834”“模板”可持久化线段树 题解报告

• 2022 年 6 月 6 日
• 笔记

题目描述

给定n个整数构成的序列，将对于指定的闭区间查询其区间内的第k小值。

输入输出格式

输入格式

第一行包含两个正整数n,m，分别表示序列的长度和查询的个数。

第二行包含n个整数，表示这个序列各项的数字。

接下来m行每行包含三个整数l,r,k, 表示查询区间[l,r]内的第k小值。

输出格式

输出包含m行，每行一个整数，依次表示每一次查询的结果

输入输出样例

输入样例

5 5
5957 6405 15770 26287 26465 
2 2 1
3 4 1
4 5 1
1 2 2
4 4 1

输出样例

6405
15770
26287
25957
26287

题解

直接康代码吧，个人觉得注释还是蛮详细的

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+2;
int tot,n,m,l,r,k;//tot 所有节点的数量     
struct node{
	int lc,rc;//表编号为i的节点的左/右儿子的编号      
	int cnt;//表编号为i的节点所代表的区间内数字出现的次数 
}tr[N<<5]; 
int a[N],b[N];//a[i]为原数组 b[i]为排序后数组                         
int rt[N];//插入i个点后的树的根节点编号    
int build(int l,int r) {//建一个空树(所有cnt都为0) 
	int p=++tot; //p为当前节点编号 
	if(l==r) return p;
	int mid=(l+r)>>1;
	tr[p].lc=build(l,mid);
	tr[p].rc=build(mid+1,r);
	return p; //返回当前节点的编号 
}
int update(int pre,int l,int r,int x) { //pre为旧树该位置节点下标 
// x为 修改位置下标 
	int p=++tot; //新建节点
	tr[p].lc=tr[pre].lc;
	tr[p].rc=tr[pre].rc;
	tr[p].cnt=tr[pre].cnt+1;
	//copy 原节点信息 
	if(l==r) return p;//到达底层，回溯 
	int mid=(l+r)>>1;
	if(x<=mid) tr[p].lc=update(tr[pre].lc,l,mid,x);
	//x出现在左子树 因此右子树保持与旧树相同 修改左子树 
	else tr[p].rc=update(tr[pre].rc,mid+1,r,x);
	//否则前往右子树 
	return p;//返回线段树中的编号 
}
int ask(int u,int v,int l,int r,int k) {
	//在u,v两个节点上，数域为[l,r]，求第k小数 
	if(l==r) return b[l]; //找到第k小 l/r是节点编号 所以答案是b[l/r] 
	int mid=(l+r)>>1;
	int p=tr[tr[v].lc].cnt-tr[tr[u].lc].cnt;
	//则p= (1~r)树的左节点数字出现的次数 - (1~(l-1))树的左节点数字出现的次数 
	//即p等于([l,r])树左儿子数字出现的次数 
	if(p>=k) return ask(tr[u].lc,tr[v].lc,l,mid,k);
	//第k小的数字在左子树处 
	else return ask(tr[u].rc,tr[v].rc,mid+1,r,k-p);
	//否则去右子树处找第k-p小的数字 
}
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+1+n); 
	int size=unique(b+1,b+1+n)-b-1; 
    //size为线段树维护的数组的大小,即b数组中不重复的数字的个数
	rt[0]=build(1,size); //初始化 建立一颗空树 并把该树的根节点的编号赋值给rt[0]
	for(int i=1;i<=n;i++){
		int x=lower_bound(b+1,b+1+size,a[i])-b;
		//在b的 [1,size+1)--->[1,size] 中二分查找第一个大于等于a[i]的b[x]
		rt[i]=update(rt[i-1],1,size,x);
		//更新a[i]带来的影响 
		//并将新树的根节点的编号赋值给rt[i] 
	}
	while(m--){
		scanf("%d%d%d",&l,&r,&k);
		int ans=ask(rt[l-1],rt[r],1,size,k);
		printf("%d\n",ans); 
	}
	return 0;
}

完结撒花❀