hdu2665-Kth number

Kth number

Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4585 Accepted Submission(s): 1461

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

Source

HDU男生专场公开赛——赶在女生之前先过节（From WHU）

Recommend

zty | We have carefully selected several similar problems for you: 2660 2662 2667 2663 2661

一開始用归并树超时了，仅仅好去学划分树= = 妈蛋，看了好久才理解。

划分树建树的原理和归并树有点类似。仅仅只是划分树採用的是高速排序的方式，先把原数列排序，建树的时候以中间大的数为基数。将小的扔左边，大的扔右边，有一些小细节，如有多个数与基数同样的时候，须要一个暂时变量记录一下，用seg[dep][i] 记录i到左边区间有多少个数是小于基数的，查询的时候，推断区间还有就

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 100000+10;

struct node{
    int lson,rson;
    int mid(){
        return (lson+rson)>>1;
    }
}tree[maxn*4];

int seg[25][maxn];
int lftnum[25][maxn];
int num[maxn];
int n,m,sta,ed;

void build(int L,int R,int rt,int dep){
    tree[rt].lson = L;
    tree[rt].rson = R;
    if(L==R) return;
    int mid = tree[rt].mid(),key = num[mid],scnt = mid-L+1;//左边中间值的个数
    for(int i = L; i <= R ; i++){
        if(seg[dep][i] < num[mid]){
            scnt--;
        }
    }
    int lp = L,rp = mid+1;
    for(int i = L; i <= R; i++){
        if(i==L){
            lftnum[dep][i] = 0;
        }else{
            lftnum[dep][i] = lftnum[dep][i-1];
        }
        if(seg[dep][i] < key){
            lftnum[dep][i]++;
            seg[dep+1][lp++] = seg[dep][i];
        }
        else if(seg[dep][i] > key){
            seg[dep+1][rp++] = seg[dep][i];
        }
        else{
            if(scnt>0){
                scnt--;
                lftnum[dep][i]++;
                seg[dep+1][lp++] = seg[dep][i];
            }else{
                seg[dep+1][rp++] = seg[dep][i];
            }
        }
    }
    build(L,mid,rt<<1,dep+1);
    build(mid+1,R,rt<<1|1,dep+1);
}
int query(int L,int R,int rt,int dep,int k){
    if(tree[rt].lson==tree[rt].rson){
        return seg[dep][L];
    }
    int cnt,act;
    if(L==tree[rt].lson){
        cnt = lftnum[dep][R];
        act = 0;
    }else{
        cnt = lftnum[dep][R] - lftnum[dep][L-1];
        act = lftnum[dep][L-1];
    }
    int mid = tree[rt].mid();
    if(cnt >= k){
        L = tree[rt].lson + act;
        R = tree[rt].lson + act + cnt-1;
        return query(L,R,rt<<1,dep+1,k);
    }else{
        int a = L-tree[rt].lson-act;
        int b = R-L-cnt+1;
        L = mid + a + 1;
        R = mid + a + b;
        return query(L,R,rt<<1|1,dep+1,k-cnt);
    }

}
int main(){
    int ncase;
    cin >> ncase;
    while(ncase--){
        cin >> n >> m;
        for(int i = 1; i <= n; i++){
            scanf("%d",&num[i]);
            seg[0][i] = num[i];
        }
        sort(num+1,num+n+1);
        build(1,n,1,0);
        while(m--){
            int k;
            scanf("%d%d%d",&sta,&ed,&k);
            printf("%d
",query(sta,ed,1,0,k));
        }
    }
    return 0;
}