[POJ] 2104. K-th Number

題目連結:http://poj.org/problem?id=2104

---

裸的區間第K大值，曾經會過可是又忘記了，只記得關鍵字持久化，被雷了才知道。原來就是原本的序列第K大是直接用樹上的節點作二分搜，但是區間的話就變成要用$[L,R]$的和做節點二分搜，而要算$[L,R]$的和，其實就用持久化線段樹把$roots[R]-roots[L]$即可。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
#define PB push_back
#define ALL(x) (x).begin(), (x).end()

const int N = 100000 + 5;
const int MEM = 2000000;

class LiSan{
	private:
		vector<int> v;
	public:
		inline void init(){v.clear();}
		inline void insert(int x){v.PB(x);}
		inline int size(){return v.size();}
		inline void done(){
			sort(ALL(v));
			v.resize(distance(v.begin(), unique(ALL(v))));
		}
		inline int get(int x){
			return distance(v.begin(), lower_bound(ALL(v), x));
		}
		inline int inv_get(int x){return v[x];}
} lisan;

class PSegTree{
	private:
		struct Node{
			int val, lc, rc;
			Node(){val=0;lc=-1;rc=-1;}
		} nodes[MEM];
		int _mem, size;
		int _new(){
			assert(_mem < MEM);
			nodes[_mem]=Node();
			return _mem++;
		}
		inline int lc(int x){return nodes[x].lc;}
		inline int rc(int x){return nodes[x].rc;}
		int build(int l, int r, int id){
			id = _new();
			if(r-l>1){
				int mid=(l+r)>>1;
				nodes[id].lc = build(l, mid, -1);
				nodes[id].rc = build(mid, r, -1);
			}
			return id;
		}
		int modify(int ql, int qr, int l, int r, int v, int id){
			if(qr <= l or r <= ql) return id;
			int nid = _new();
			if(ql <= l and r <= qr){
				nodes[nid] = nodes[id];
				nodes[nid].val += v;
				return nid;
			}
			int mid = (l+r)>>1;
			nodes[nid].lc = modify(ql, qr, l, mid, v, nodes[id].lc);
			nodes[nid].rc = modify(ql, qr, mid, r, v, nodes[id].rc);
			nodes[nid].val = nodes[nodes[nid].lc].val + nodes[nodes[nid].rc].val;
			return nid;
		}
		int query(int k, int l, int r, int idL, int idR){
			if(r-l==1) return l;
			int lV = nodes[lc(idR)].val - nodes[lc(idL)].val;
			int mid=(l+r)>>1;
			if(lV >= k)
				return query(k, l, mid, lc(idL), lc(idR));
			else
				return query(k-lV, mid, r, rc(idL), rc(idR));
		}
	public:
		int build(int n){
			_mem=0;
			size=n;
			return build(0, n, -1);
		}
		int modify(int p, int v, int id){
			return modify(p, p+1, 0, size, v, id);
		}
		int query(int k, int idL, int idR){
			return query(k, 0, size, idL, idR);
		}
};

PSegTree seg;
int arr[N], roots[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, q; cin>>n>>q;
	lisan.init();
	for(int i=0;i<n;i++){
		cin>>arr[i];
		lisan.insert(arr[i]);
	}
	lisan.done();
	roots[0]=seg.build(lisan.size());
	for(int i=0;i<n;i++)
		roots[i+1] = seg.modify(lisan.get(arr[i]),1,roots[i]);
	for(int i=0;i<q;i++){
		int l, r, k; cin>>l>>r>>k;
		int res = seg.query(k, roots[l-1], roots[r]);
		cout<<lisan.inv_get(res)<<'\n';
	}
	return 0;
}