Kth number HDU - 2665 지속 가능 한 선분 트 리 주석 트 리

#include 
#include 
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;
const int MAXM = 2e6 + 10; //  q*logn   RE     
int root[MAXN], son[MAXM][2], idx; //                 
int a[MAXN], val[MAXM]; //        
vector<int> dz; //   

void Update(int old, int &x, int l, int r, int v) // old            v            
{
	x = ++idx; //x   
	son[x][0] = son[old][0], son[x][1] = son[old][1], val[x] = val[old] + 1; //          +1
	if (l == r)
		return;
	int m = l + r >> 1;
	if (m >= v)
		Update(son[x][0], son[x][0], l, m, v);
	else
		Update(son[x][1], son[x][1], m + 1, r, v);
}
int Query(int old, int &x, int l, int r, int k) //  [old, x]   k 
{
	if (l == r)
		return l; //    
	int m = l + r >> 1;
	int lef = val[son[x][0]] - val[son[old][0]]; //        
	if (k <= lef) //    
		return Query(son[old][0], son[x][0], l, m, k); // old x         
	else
		return Query(son[old][1], son[x][1], m + 1, r, k - lef); //       
}
int Dis(int v)
{
	return lower_bound(dz.begin(), dz.end(), v) - dz.begin();
}
int main()
{
#ifdef LOCAL
	freopen("C:/input.txt", "r", stdin);
#endif
	int T;
	cin >> T;
	while (T--)
	{
		dz.clear();
		dz.push_back(INT_MIN);
		idx = 0; //  ??
		int N, M;
		cin >> N >> M;
		for (int i = 1; i <= N; i++)
			scanf("%d", &a[i]), dz.push_back(a[i]);
		sort(dz.begin(), dz.end());
		dz.erase(unique(dz.begin(), dz.end()), dz.end());
		for (int i = 1; i <= N; i++)
			Update(root[i - 1], root[i], 1, dz.size(), Dis(a[i])); //     
		for (int i = 0; i < M; i++)
		{
			int l, r, k;
			scanf("%d%d%d", &l, &r, &k);
			printf("%d
", dz[Query(root[l - 1], root[r], 1, dz.size(), k)]); //        
		}
	}

	return 0;
}