# 11114: 【原1114】Problem A

### 题目描述

author: Zheyi Pan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1114

## Sample Input

``````5
1 2 3 4 5
3
1 3 2
1 4 1
2 5 4
``````

## Sample Output

``````2
1
5
``````

## Restrictions

60%： n, m <= 1000。

80%： 数据满足询问区间互相不包含。

100%：n, m <= 300000，|a[i]| <= 10^9。

## FineArtz's solution

``````/* Problem A */
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 300005;

class Node{
public:
int sum = 0, l = 0, r = 0;
};

int a[MAXN], s[MAXN], root[MAXN] = {0};
int cnt = 0;
Node tree[MAXN << 5];

int createNode(int sum, int l, int r){
tree[++cnt].sum  = sum;
tree[cnt].l = l;
tree[cnt].r = r;
return cnt;
}

void insert(int &root, int preroot, int pos, int l, int r){
root = createNode(tree[preroot].sum + 1, tree[preroot].l, tree[preroot].r);
if (l == r)
return;
int mid = (l + r) / 2;
if (pos <= mid)
insert(tree[root].l, tree[preroot].l, pos, l, mid);
else
insert(tree[root].r, tree[preroot].r, pos, mid + 1, r);
}

int query(int left, int right, int k, int l, int r){
if (l == r)
return l;
int mid = (l + r) / 2;
int sum = tree[tree[right].l].sum - tree[tree[left].l].sum;
if (k <= sum)
return query(tree[left].l, tree[right].l, k, l, mid);
else
return query(tree[left].r, tree[right].r, k - sum, mid + 1, r);
}

int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n;
for (int i = 1; i <= n; ++i){
cin >> a[i];
s[i] = a[i];
}
sort(s + 1, s + n + 1);
int num = unique(s + 1, s + n + 1) - (s + 1);
for (int i = 1; i <= n; ++i){
int pos = lower_bound(s + 1, s + num + 1, a[i]) - s;
insert(root[i], root[i - 1], pos, 1, num);
}
cin >> m;
while (m--){
int x, y, k;
cin >> x >> y >> k;
int t = query(root[x - 1], root[y], k, 1, num);
cout << s[t] << '\n';
}
return 0;
}
``````

## yyong119's solution

``````#include <cstdio>
#include <algorithm>
#define MAX 300010
using namespace std;
const int INF = 0xFFFFFFF;
int nums[MAX], sorted[MAX], root[MAX];
int cnt;
struct TMD {
int sum, L_son, R_son;
} Tree[MAX << 5];

inline int CreateNode(int _sum, int _L_son, int _R_son) {

int idx = ++cnt;
Tree[idx].sum = _sum;
Tree[idx].L_son = _L_son;
Tree[idx].R_son = _R_son;
return idx;
}

void Insert(int & root, int pre_rt, int pos, int L, int R) {

root = CreateNode(Tree[pre_rt].sum + 1, Tree[pre_rt].L_son, Tree[pre_rt].R_son);
if (L == R) return;
int M = (L + R) >> 1;
if (pos <= M)
Insert(Tree[root].L_son, Tree[pre_rt].L_son, pos, L, M);
else
Insert(Tree[root].R_son, Tree[pre_rt].R_son, pos, M + 1, R);
}

int Query(int S, int E, int L, int R, int K) {

if (L == R) return L;
int M = (L + R) >> 1;
int sum = Tree[Tree[E].L_son].sum - Tree[Tree[S].L_son].sum;
if (K <= sum)
return Query(Tree[S].L_son, Tree[E].L_son, L, M, K);
else
return Query(Tree[S].R_son, Tree[E].R_son, M + 1, R, K - sum);
}

int main() {

int n, m, num, pos, T;
scanf("%d", &n);
cnt = 0; root[0] = 0;
for (int i = 1; i <= n; ++i) {
scanf("%d", &nums[i]);
sorted[i] = nums[i];
}
sort(sorted + 1, sorted + 1 + n);
num = unique(sorted + 1, sorted + n + 1) - (sorted + 1);
for (int i = 1; i <= n; ++i) {
pos = lower_bound(sorted + 1, sorted + num + 1, nums[i]) - sorted;
Insert(root[i], root[i - 1], pos, 1, num);
}
scanf("%d", &m);
int l, r, k;
while (m--) {
scanf("%d %d %d", &l, &r, &k);
pos = Query(root[l - 1], root[r], 1, num, k);
printf("%d\n", sorted[pos]);
}
return 0;
}
``````