POJ 2104 K-th Number 靜態主席樹（裸

題目鏈接：點擊打開鏈接

題意：

給定n長的序列，q個詢問

下面n個數字給出序列

每個詢問[l, r] k ，輸出該區間中第k大的數

先建一個n個節點的空樹，然後每次從後往前新建一棵樹，依附原來的空樹建。詢問就是在樹上二分。

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 100010;
const int M = N * 30;
int n, q, tot;
int a[N];
int T[M], lson[M], rson[M], c[M];
vectorG;

void input(){
	G.clear();
	for (int i = 1; i <= n; i++)scanf("%d", &a[i]), G.push_back(a[i]);
	sort(G.begin(), G.end());
	G.erase(unique(G.begin(), G.end()), G.end());
	for (int i = 1; i <= n; i++)a[i] = lower_bound(G.begin(), G.end(), a[i]) - G.begin() + 1;
}
int build(int l, int r){
	int root = tot++;
	c[root] = 0;
	if (l != r){
		int mid = (l + r) >> 1;
		lson[root] = build(l, mid);
		rson[root] = build(mid + 1, r);
	}
	return root;
}
int updata(int root, int pos, int val){
	int newroot = tot++, tmp = newroot;
	c[newroot] = c[root] + val;
	int l = 1, r = G.size();
	while (l <= r){
		int mid = (l + r) >> 1;
		if (pos <= mid){
			lson[newroot] = tot++; rson[newroot] = rson[root];
			newroot = lson[newroot]; root = lson[root];
			r = mid - 1;
		}
		else {
			rson[newroot] = tot++; lson[newroot] = lson[root];
			newroot = rson[newroot]; root = rson[root];
			l = mid + 1;
		}
		c[newroot] = c[root] + val;
	}
	return tmp;
}
int query(int L, int R, int k){
	int l = 1, r = G.size(), ans = l;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (c[lson[L]] - c[lson[R]] >= k){
			ans = mid;
			r = mid - 1;
			L = lson[L];
			R = lson[R];
		}
		else {
			l = mid + 1;
			k -= c[lson[L]] - c[lson[R]];
			L = rson[L]; 
			R = rson[R];
		}
	}
	return ans;
}
int main(){
	while (~scanf("%d%d", &n, &q)){
		input();
		tot = 0;
		T[n + 1] = build(1, G.size());
		for (int i = n; i; i--)
			T[i] = updata(T[i + 1], a[i], 1);
		while (q--){
			int l, r, k; scanf("%d %d %d", &l, &r, &k);
			printf("%d\n", G[query(T[l], T[r+1], k)- 1]);
		}
	}
	return 0;
}