[7469] K번째 수

https://www.acmicpc.net/problem/7469

---

Persistent Segment Tree와 비슷한 Persistent Indexed Tree(?)를 구현해서 통과했다.

실제로 구현해 본 건 처음이었는데 예전에 명우씨한테 잠깐 설명들었던게 도움이 됐다. 

(Persistent Segment Tree에 대한 설명은 요기에)

vector로 내맘대로 구현했는데, lower_bound썼으면 좀 더 깔끔했을듯.. 시간복잡도는 O(Mlog²N)

자세한 설명은 다음에...

테스트케이스 : kth.zip(출처 : NEERC Subregional Contest)

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <functional>
#define MAXN 262150
#define INF 1987654321
using namespace std;
struct st{
	int mx, cnt, idx;
};
vector <st> tree[MAXN];
int n, m, sz;
pair <int, int> arr[100004];
__inline int max(int a, int b){ return a > b ? a : b; }
void cand_add(vector<st> &v, int idx, int p){
	int low = 0;
	int hi = tree[idx].size() - 1;
	st ret = { NULL };
	while (low <= hi){
		int mid = (low + hi) >> 1;
		if (tree[idx][mid].idx > p) 
			hi = mid - 1;
		else{
			ret = tree[idx][mid];
			low = mid + 1;
		}
	}
	if (ret.cnt)
		v.push_back(ret);
}
int main(){
	scanf("%d%d", &n, &m);
	for (sz = 1; sz < n; sz <<= 1);
	sz--;
	for (int i = 1; i <= n; i++){
		scanf("%d", &arr[i].first);
		arr[i].second = i;
	}
	sort(arr + 1, arr + n + 1);
	for (int i = 1; i <= n; i++){
		int p = sz + arr[i].second;
		tree[p].push_back({ arr[i].first, 1, i });
		p >>= 1;
		while (p){
			tree[p].push_back({
				max(tree[p << 1].size() ? (tree[p << 1].end() - 1)->mx : -INF, tree[(p << 1) + 1].size() ? (tree[(p << 1) + 1].end() - 1)->mx : -INF),
				(tree[p << 1].size() ? (tree[p << 1].end() - 1)->cnt : 0) + (tree[(p << 1) + 1].size() ? (tree[(p << 1) + 1].end() - 1)->cnt : 0),
				i
			});
			p >>= 1;
		}
	}
	for (int i = 1; i <= m; i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		int t_low = 1;
		int t_hi = n;
		while (t_low <= t_hi){
			vector <st> cand;
			int t_mid = (t_low + t_hi) >> 1;
			int low = sz + a;
			int hi = sz + b;
			while (low <= hi){
				if (low & 1) cand_add(cand, low, t_mid);
				if (!(hi & 1)) cand_add(cand, hi, t_mid);
				low = (low + 1) >> 1;
				hi = (hi - 1) >> 1;
			}
			int total = 0;
			for (auto it : cand)
				total += it.cnt;
			if (total < c) t_low = t_mid + 1;
			else if (total>c) t_hi = t_mid - 1;
			else{
				int ans = -INF;
				for (auto it : cand)
					ans = max(ans, it.mx);
				printf("%d\n", ans);
				break;
			}
		}
	}
}