Kth number
Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Problem Description
Give you a sequence and ask you the kth big number of a inteval.
Input
The first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]
Output
For each test case, output m lines. Each line contains the kth big number.
Sample Input
1
10 1
1 4 2 3 5 6 7 8 9 0
1 3 2
Sample Output
2
题意:
和poj2104差不多这里就不多写了,这里是题解:查看题解
需要注意的是cnt和vector的初始化。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 1e+5 + 10;
struct NODE {
int l;
int r;
int sum;
};
NODE T[maxn * 50];
int root[maxn], a[maxn];
int cnt = 0;
vector<int> v;
int GetId(int x) {
return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}
void Updata(int l, int r, int &x, int y, int pos) {
T[++cnt] = T[y];
T[cnt].sum++;
x = cnt;
if (l == r) return ;
int mid = (l + r) >> 1;
if (mid >= pos) Updata(l, mid, T[x].l, T[y].l, pos);
else Updata(mid + 1, r, T[x].r, T[y].r, pos);
}
int Query(int l, int r, int x, int y, int k) {
if (l == r) return l;
int mid = (l + r) >> 1;
int sum = T[T[y].l].sum - T[T[x].l].sum;
if (sum >= k) return Query(l, mid, T[x].l, T[y].l, k);
else return Query(mid + 1, r, T[x].r, T[y].r, k - sum);
}
int main() {
int n, t, m;
scanf("%d", &t);
while (t--) {
cnt = 0;
v.clear();
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
v.push_back(a[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 1; i <= n; i++) Updata(1, n, root[i], root[i - 1], GetId(a[i]));
while (m--) {
int x, y, k;
scanf("%d %d %d", &x, &y, &k);
printf("%d\n", v[Query(1, n, root[x - 1], root[y], k) - 1]);
}
}
return 0;
}