[题目链接]
http://poj.org/problem?id=2104
[算法]
考虑离线 , 将询问按右端点排序
对于每个询问(l , r , k) , 若我们知道区间[l , r]中 <= x的数有多少个 , 就可以通过二分解决
进一步 , 我们可以将区间[l , r]中 <= x 的数的个数转化为区间[1 , r]中 <= x的数的个数 - 区间[1 , l - 1]中 <= x的数的个数
那么 , 我们只需维护一个数据结构 , 支持询问任意一段左端点为1的区间中 <= x的数的个数 。 可持久化线段树可以完成这个任务
时间复杂度 : O(MlogN)
[代码]
#include<bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 10; struct query { int l , r , k; int id; } q[MAXN]; int n , m , idx; int tmp[MAXN] , lson[MAXN << 5] , rson[MAXN << 5] , sum[MAXN << 5] , root[MAXN] , ans[MAXN] , a[MAXN]; template <typename T> inline void chkmax(T &x,T y) { x = max(x,y); } template <typename T> inline void chkmin(T &x,T y) { x = min(x,y); } template <typename T> inline void read(T &x) { T f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } inline bool cmp(query a , query b) { return a.r < b.r; } inline void build(int &k , int l , int r) { k = ++idx; if (l == r) return; int mid = (l + r) >> 1; build(lson[k] , l , mid); build(rson[k] , mid + 1 , r); } inline void modify(int &k , int old , int l , int r , int pos , int value) { k = ++idx; lson[k] = lson[old] , rson[k] = rson[old]; sum[k] = sum[old] + value; if (l == r) return; int mid = (l + r) >> 1; if (mid >= pos) modify(lson[k] , lson[k] , l , mid , pos , value); else modify(rson[k] , rson[k] , mid + 1 , r , pos , value); } inline int query(int rt1 , int rt2 , int l , int r , int k) { if (l == r) return l; int tmp = sum[lson[rt1]] - sum[lson[rt2]]; int mid = (l + r) >> 1; if (tmp >= k) return query(lson[rt1] , lson[rt2] , l , mid , k); else return query(rson[rt1] , rson[rt2] , mid + 1 , r , k - tmp); } int main() { read(n); read(m); for (int i = 1; i <= n; i++) { read(a[i]); tmp[i] = a[i]; } sort(tmp + 1 , tmp + n + 1); int len = unique(tmp + 1 , tmp + n + 1) - tmp - 1; for (int i = 1; i <= n; i++) a[i] = lower_bound(tmp + 1 , tmp + len + 1 , a[i]) - tmp; build(root[0] , 1 , len); for (int i = 1; i <= m; i++) { read(q[i].l); read(q[i].r); read(q[i].k); q[i].id = i; } sort(q + 1 , q + m + 1 , cmp); int now = 1; for (int i = 1; i <= n; i++) { modify(root[i] , root[i - 1] , 1 , n , a[i] , 1); while (now <= m && q[now].r == i) ans[q[now].id] = tmp[query(root[i] , root[q[now].l - 1] , 1 , n , q[now].k)] , ++now; } for (int i = 1; i <= m; i++) printf("%d " , ans[i]); return 0; }