记录编号	562420	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	3537.[POJ 2104]第k小的数	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.634 s
提交时间	2021-07-05 09:15:18	内存使用	11.00 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200005; 
struct Q{
    int l,r,k;
    int op,id;
    Q() {
        l = r = k = 0;
        op = id = 0;
    }
}query[maxn],lq[maxn],rq[maxn];
int n,m;
int c[maxn];
int lowbit(int x) {
    return x & -x;
}
void add(int x,int y) {
    for(;x <= n;x += lowbit(x)) {
        c[x] += y;
    }
    return ;
}
int ask(int x) {
    int tot = 0;
    for(;x;x -= lowbit(x)) {
        tot += c[x];
    }
    return tot;
}
int ans[maxn];
int C[maxn],cnt;
void solve(int l,int r,int x,int y) {
    if(x > y)return ;
    if(l == r) {
        for(int i = x;i <= y;++ i) {
            if(query[i].op)ans[query[i].id] = C[l];
        }
        return ;
    }
    int mid = l + r >> 1;
    int lt = 0,rt = 0;
    for(int i = x;i <= y;++ i) {
        if(!query[i].op) {
            if(query[i].k <= mid) {
                add(query[i].id , 1);
                lq[++ lt] = query[i];
            }
            else rq[++ rt] = query[i];
        }
        else {
            int cnt = ask(query[i].r ) - ask(query[i].l - 1);
            if(ask(query[i].r) - ask(query[i].l - 1) >= query[i].k) {
                lq[++ lt] = query[i];
            }
            else query[i].k -= cnt,rq[++ rt] = query[i];
        }       
    }     
    for(int i = x;i <= y;++ i) {
        if(!query[i].op) {
            if(query[i].k <= mid) {
                add(query[i].id , -1);
            }
        }
    }
    for(int i = 1;i <= lt;++ i) {
        query[x + i - 1] = lq[i];
    }
    for(int i = 1;i <= rt;++ i) {
        query[x + lt + i - 1] = rq[i];
    }
    solve(l , mid , x , x + lt - 1);
    solve(mid + 1 , r , x + lt , y);
    return ;
}
int main() {
    freopen("knumber.in","r",stdin);
    freopen("knumber.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++ i) {
        scanf("%d",&query[i].k);
        query[i].id = i;
        query[i].op = 0;
        C[i] = query[i].k;
    }
    for(int i = n + 1;i <= n + m;++ i) {
        scanf("%d%d%d",&query[i].l,&query[i].r,&query[i].k);
        query[i].id = i;
        query[i].op = 1;
    }
    sort(C + 1 , C + 1 + n);
    cnt = unique(C + 1 , C + 1 + n) - C - 1;
    for(int i = 1;i <= n;++ i) {
        query[i].k = lower_bound(C + 1 , C + 1 + cnt , query[i].k) - C;
    }
    solve(1 , cnt , 1 , n + m);
    for(int i = n + 1;i <= n + m;++ i) {
        printf("%d\n",ans[i]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}