参考：《挑战程序设计竞赛》P188
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #include <queue> #include <vector> #include <stack> #include <map> #include <set> #include <cmath> #include <cctype> #include <ctime> #include <cassert> using namespace std; #define REP(i, n) for (int i = 0; i < (n); ++i) #define eps 1e-9 #define Left _id << 1 #define Right _id << 1 | 1 #define lson low, mid, Left #define rson mid + 1, high, Right typedef long long ll; typedef pair<int, int> pii; const int maxn = 1e5 + 10; int n, m, x, y, k; int a[maxn], a_sorted[maxn]; vector<int> tree[1 << 18]; void build(int low, int high, int _id); int query(int l, int r, int key, int low, int high, int _id); int main() { #ifdef __AiR_H freopen("in.txt", "r", stdin); // freopen("out3.txt", "w", stdout); #endif // __AiR_H scanf("%d %d", &n, &m); for (int i = 1; i <= n; ++i) { scanf("%d", &a[i]); a_sorted[i] = a[i]; } sort(a_sorted + 1, a_sorted + 1 + n); build(1, n, 1); int low, high, mid; while (m--) { scanf("%d %d %d", &x, &y, &k); low = 0; high = n; while (high - low > 1) { mid = low + (high - low) / 2; if (query(x, y, a_sorted[mid], 1, n, 1) >= k) { high = mid; } else { low = mid; } } printf("%d\n", a_sorted[high]); } #ifdef __AiR_H printf("Time used = %.2fs\n", (double)clock() / CLOCKS_PER_SEC); #endif // __AiR_H return 0; } int query(int l, int r, int key, int low, int high, int _id) { if (l == low && r == high) { return upper_bound(tree[_id].begin(), tree[_id].end(), key) - tree[_id].begin(); } int mid = low + (high - low) / 2; if (r <= mid) { return query(l, r, key, lson); } else if (l >= mid + 1) { return query(l, r, key, rson); } else { return query(l, mid, key, lson) + query(mid + 1, r, key, rson); } } void build(int low, int high, int _id) { if (low == high) { tree[_id].push_back(a[low]); return; } int mid = low + (high - low) / 2; build(lson); build(rson); tree[_id].resize(high - low + 1); merge(tree[Left].begin(), tree[Left].end(), tree[Right].begin(), tree[Right].end(), tree[_id].begin()); }
