|
|
題目鏈接：http://poj.org/problem?id=2761
  /**//*
 題意：
給出一個長度為N(N <= 100000)的數(shù)列，然后是一連串詢問，詢問數(shù)
<= 50000，詢問的格式是a, b, k，問[a, b]區(qū)間中的k小數(shù)。
解法：
二分+樹狀數(shù)組 或者 二分+歸并樹+線段樹
思路：
這題的解法比較多，可以練習各種數(shù)據(jù)結(jié)構(gòu)，不知是不是我的線段樹
效率比較低，用線段樹一直過不去，這題和PKU 2104有個區(qū)別就是給定的
詢問區(qū)間不會互相包含，于是就可以用樹狀數(shù)組求解，雖然復雜度很接近
，但是樹狀數(shù)組的常數(shù)小得多。
來看看具體的解法：首先將讀進來的N個數(shù)離散化，可以用二分或者
hash或者先排序一遍記錄下標皆可。然后讀入的M個區(qū)間詢問進行對X軸遞
增排序，注意需要記錄下當前詢問的下標，以便之后輸出答案。對于讀入
的M個區(qū)間進行線性掃描，對第一個區(qū)間[x0,y0]中的所有數(shù)插入到樹狀數(shù)
組中，即調(diào)用add(val, 1)，其x0 <= val <= y0，然后二分查找第k大數(shù)，
這個復雜度是O(logNlogN)的，對于下一個區(qū)間[x1,y1]，如果這兩個區(qū)間
有相交部分，那么顯然這部分不用操作，我們知道對，[x0,y0]中有但
[x1,y1]中沒有的部分進行刪除操作，即調(diào)用add(val, -1)，而對[x1,y1]
中有但[x0,y0]中沒有的部分進行添加操作，即調(diào)用add(val, 1)。每次添
加完畢后進行統(tǒng)計。最后輸出答案即可。注意輸出的時候要小心，下標之
間的映射。
 */
#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);
// 將上一個區(qū)間剩余的數(shù)去掉
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);
}
// 加入這個區(qū)間新增的數(shù)
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
*/
|