「洛谷 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;
}

完結撒花❀