|
|
题目链接：http://poj.org/problem?id=2761
  /**//*
 题意：
给出一个长度为N(N <= 100000)的数列，然后是一连串询问，询问数
<= 50000，询问的格式是a, b, k，问[a, b]区间中的k小数。
解法：
二分+树状数组 或者 二分+归并树+线段树
思路：
这题的解法比较多，可以练习各种数据结构，不知是不是我的线段树
效率比较低，用线段树一直过不去，这题和PKU 2104有个区别就是给定的
询问区间不会互相包含，于是就可以用树状数组求解，虽然复杂度很接近
，但是树状数组的常数小得多。
来看看具体的解法：首先将读进来的N个数离散化，可以用二分或者
hash或者先排序一遍记录下标皆可。然后读入的M个区间询问进行对X轴递
增排序，注意需要记录下当前询问的下标，以便之后输出答案。对于读入
的M个区间进行线性扫描，对第一个区间[x0,y0]中的所有数插入到树状数
组中，即调用add(val, 1)，其x0 <= val <= y0，然后二分查找第k大数，
这个复杂度是O(logNlogN)的，对于下一个区间[x1,y1]，如果这两个区间
有相交部分，那么显然这部分不用操作，我们知道对，[x0,y0]中有但
[x1,y1]中没有的部分进行删除操作，即调用add(val, -1)，而对[x1,y1]
中有但[x0,y0]中没有的部分进行添加操作，即调用add(val, 1)。每次添
加完毕后进行统计。最后输出答案即可。注意输出的时候要小心，下标之
间的映射。
 */
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 100010
struct Value  {
int val;
int idx;
}V[maxn];
struct Intval {
int l, r, k;
int idx;
}I[maxn];
int ID[maxn];
struct TreeArray {
int data[maxn];
int MaxVal;
  void setMaxVal(int _v) {
MaxVal = _v;
 }
void clear() {
MaxVal = maxn - 1;
for(int i = 1; i < maxn; i++) {
data[i] = 0;
}
}
int lowbit(int x) {
return x & (-x);
}
void add(int pos, int val) {
while(pos && pos <= MaxVal) {
data[pos] += val;
pos += lowbit(pos);
}
}
int sum(int pos) {
int s = 0;
while(pos >= 1) {
s += data[pos];
pos -= lowbit(pos);
}
return s;
}
int Query(int K) {
int l = 1;
int h = MaxVal;
int ans = 0;
while(l <= h) {
int m = (l + h) >> 1;
if(sum(m-1) < K) {
l = m + 1;
if(m > ans)
ans = m;
}else
h = m - 1;
}
return ans;
}
};
int n, m;
bool cmp0(Value a, Value b) {
return a.val < b.val;
}
bool cmp1(Intval a, Intval b) {
return a.l < b.l;
}
TreeArray Tree;
int ans[ maxn ];
int Min(int a, int b) {
return a < b ? a : b;
}
int Max(int a, int b) {
return a > b ? a : b;
}
int main() {
int i, j;
while(scanf("%d %d", &n, &m) != EOF) {
for(i = 1; i <= n; i++) {
scanf("%d", &V[i].val);
V[i].idx = i;
}
sort(V+1, V+n+1, cmp0);
for(i = 1; i <= n; i++) {
ID[V[i].idx] = i;
}
for(i = 1; i <= m; i++) {
scanf("%d %d %d", &I[i].l, &I[i].r, &I[i].k);
if(I[i].l > I[i].r) {
swap(I[i].l, I[i].r);
}
I[i].idx = i;
}
sort(I+1, I+m+1, cmp1);
Tree.clear();
Tree.setMaxVal(n);
I[0].l = I[0].r = 0;
for(i = 1; i <= m; i++) {
int MinSub = Min(I[i-1].r, I[i].l-1);
// 将上一个区间剩余的数去掉
for(j = I[i-1].l; j <= MinSub; j++) {
Tree.add(ID[j], -1);
}
for(j = I[i].r+1; j <= I[i-1].r; j++) {
Tree.add(ID[j], -1);
}
// 加入这个区间新增的数
int MaxAdd = Max(I[i-1].r+1, I[i].l);
for(j = MaxAdd; j <= I[i].r; j++) {
Tree.add(ID[j], 1);
}
ans[ I[i].idx ] = V[ Tree.Query(I[i].k) ].val;
}
for(i = 1; i <= m; i++) {
printf("%d\n", ans[i]);
}
}
return 0;
}
/**//*
7 6
1 5 2 2 2 7 4
2 7 1
2 7 2
2 7 3
2 7 4
2 7 5
2 7 6
*/
|