區間第K小（可持久化線段樹）

目錄

• 問題
• 分析
• 代碼
• • 一般形式
  • 簡化形式

問題

• 給定一個序列 a 1 ， a 2 ， ⋯ ， a n a_1，a_2，\cdots，a_n a1​，a2​，⋯，an​， m m m 次操作，每次給定 l ， r ， k l，r，k l，r，k，問 a l ， a l + 1 ， ⋯ ， a r a_l，a_{l+1}，\cdots ，a_r al​，al+1​，⋯，ar​中第 k k k 小的值.
  • 1 ≤ a i ≤ n 1 \leq a_i \leq n 1≤ai​≤n
  • 1 ≤ n ， m ≤ 100000 1\leq n，m \leq 100000 1≤n，m≤100000
  • 1 ≤ l ≤ r ≤ n ， 1 ≤ k ≤ r − l + 1 1\leq l \leq r\leq n，1\leq k \leq r-l+1 1≤l≤r≤n，1≤k≤r−l+1

分析

• 序 → \rightarrow → 時間
• n棵線段樹維護各個時刻的各個數字的出現次數
• 增量持久化政策優化線段樹

代碼

一般形式

#include<bits/stdc++.h>
using namespace std;
const int MXN = 1e5+5;
int N, M, tot, ver[MXN];
struct TreeNode{
	int l, r, sum;
}tree[MXN*20];
int build(int l, int r){
	int root = ++tot;
	tree[root].sum = 0;
	if(l == r) return root;
	int mid = (l+r)>>1;
	tree[root].l = build(l, mid); // 左子樹
	tree[root].r = build(mid+1, r); // 右子樹
	return root;
}
void pushup(int root){
	TreeNode &rt = tree[root];
	TreeNode &ls = tree[rt.l], &rs = tree[rt.r];
	rt.sum = ls.sum + rs.sum;
}
int change(int node, int l, int r, int pos){ // node：待更新的子樹
	int root = ++tot;
	TreeNode &rt = tree[root];
	rt = tree[node]; // 複制
	if(l == r){
		rt.sum += 1;
		return root;
	}
	int mid = (l+r)>>1;
	if(pos <= mid) rt.l = change(rt.l, l, mid, pos);
	else rt.r = change(rt.r, mid+1, r, pos);
	pushup(root); // 上推更新
	return root;
}
int query(int pre, int lst, int l, int r, int k){
	if(l == r) return r;
	TreeNode &pn = tree[pre], &ln = tree[lst];
	int x = tree[ln.l].sum - tree[pn.l].sum;
	int mid = (l+r)>>1;
	if(x >= k) return query(pn.l, ln.l, l, mid, k);
	else return query(pn.r, ln.r, mid+1, r, k-x);
}
int main(){
	int t, x, L, R, K;
	scanf("%d", &t);	
	while(t--){
		tot = 0;
		scanf("%d%d", &N, &M);
		ver[0] = build(1, N);       
		for(int i = 1; i <= N; ++i){
			scanf("%d", &x);		
			ver[i] = change(ver[i-1], 1, N, x);
		}
		while(M--){
			scanf("%d%d%d", &L, &R, &K);
			printf("%d\n", query(ver[L-1], ver[R], 1, N, K));
		}
	}
    return 0;
}
           

簡化形式

#include<bits/stdc++.h>
using namespace std;
const int MXN = 1e5+5;
int N, M, tot, ver[MXN];
struct TreeNode{
	int l, r, sum;
}tree[MXN*20];
int build(int l, int r){ // 初始樹
	int root = ++tot;
	tree[root].sum = 0;	
	tree[root].l = root;
	tree[root].r = root;
	return root;
}
int change(int node, int l, int r, int pos){
	int root = ++tot;
	TreeNode &rt = tree[root];
	rt = tree[node], ++rt.sum;
	if(l == r) return root;
	int mid = (l+r)>>1;
	if(pos <= mid) rt.l = change(rt.l, l, mid, pos);
	else rt.r = change(rt.r, mid+1, r, pos);
	return root;
}
int query(int pre, int lst, int l, int r, int k){
	if(l == r) return r;
	TreeNode &pn = tree[pre], &ln = tree[lst];
	int x = tree[ln.l].sum - tree[pn.l].sum;
	int mid = (l+r)>>1;
	if(x >= k) return query(pn.l, ln.l, l, mid, k);
	else return query(pn.r, ln.r, mid+1, r, k-x);
}
int main(){
	int t, x, L, R, K;
	scanf("%d", &t);	
	while(t--){
		tot = 0;
		scanf("%d%d", &N, &M);
		ver[0] = build(1, N);       
		for(int i = 1; i <= N; ++i){
			scanf("%d", &x);		
			ver[i] = change(ver[i-1], 1, N, x);
		}
		while(M--){
			scanf("%d%d%d", &L, &R, &K);
			printf("%d\n", query(ver[L-1], ver[R], 1, N, K));
		}
	}
    return 0;
}