P1533 可怜的狗狗

可持久化线段树的板子题目

1. 离散化（build）；
2. 查找（find）；

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

const int N = 3e5 + 7;
int a[N], hs[N];
int rt[N], tl[N << 6], tr[N << 6], s[N << 6], cnt = 1;

int build(int l, int r, int val, int pr){
	int p = cnt;
	s[p] = s[pr], tr[p] = tr[pr], tl[p] = tl[pr];
	s[cnt ++] ++;
	if(l == r) return p;
	int mid = (l + r) >> 1;
	if(mid >= val)tl[p] = build(l, mid, val, tl[pr]);
	else tr[p] = build(mid + 1, r, val, tr[pr]);
	return p;
}

int find(int l, int r,int x, int y, int k){
	if(l == r) return hs[l];
	int ans = s[tl[y]] - s[tl[x]];
	int mid = (l + r) >> 1;
	if(ans >= k) return find(l, mid, tl[x], tl[y], k);
	else return find(mid + 1, r, tr[x], tr[y], k - ans);
}

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1;i <= n;i ++) scanf("%d", &a[i]), hs[i] = a[i];
	sort(hs + 1, hs + n + 1);
	int t = unique(hs + 1, hs + n + 1) - hs - 1;
	
	for(int i = 1;i <= n;i ++){
		int p = lower_bound(hs + 1, hs + t + 1, a[i]) - hs;
		rt[i] = build(1, t, p, rt[i - 1]);
	}
	
	for(int i = 1;i <= m;i ++){
		int l, r, v;
		scanf("%d%d%d", &l, &r, &v);
		printf("%d\n", find(1, t, rt[l - 1], rt[r], v));
	}
	
	return 0;
}

（每周回顾！不然容易忘！）