记录编号	561108	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	3537.[POJ 2104]第k小的数	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.818 s
提交时间	2021-06-21 19:01:53	内存使用	6.54 MiB

//整体分治 
#include <cstdio> 
#include <algorithm> 
#include <cstring> 
using namespace std;  
const int maxn = 100005;  
struct rec { 
    int l,r,k; 
    int op; 
    rec() { 
        l = r = k = 0; 
        op = 0; 
    }  
}q[maxn << 1],lq[maxn << 1],rq[maxn << 1]; 
const int INF = 1e9;   
int n,m,t; 
int a[maxn],c[maxn];  
int ans[maxn];   
int lowbit(int x) {      
    return x & -x;
} 
void update(int x,int val) {
    for(int i = x;i <= n;i += lowbit(i)) {
        c[i] += val; 
    }
    return ;
} 
int ask(int x) {
    int ans = 0;
    for(;x;x -= lowbit(x)) {
        ans += c[x]; 
    }
    return ans;
} 
void solve(int l,int r,int st,int ed) {
    if(st > ed)return ;
    if(l == r) { 
        for(int i = st;i <= ed;++ i) {
            if(q[i].op) {
                ans[q[i].op] = l; 
            }
        }
        return ;  
    }
    int mid = l + r >> 1;
    int lt = 0,rt = 0;
    for(int i = st;i <= ed;++ i) {
        if(!q[i].op) {
            if(q[i].k <= mid)update(q[i].l , 1),lq[++ lt] = q[i];
            else rq[++ rt] = q[i];
        }
        else {
            int cnt = ask(q[i].r) - ask(q[i].l - 1);
            if(cnt >= q[i].k)lq[++ lt] = q[i];
            else q[i].k -= cnt,rq[++ rt] = q[i];
        }
    }
    for(int i = ed;i >= st;-- i) {
        if(!q[i].op&&q[i].k <= mid)update(q[i].l , - 1);
    }
    for(int i = 1;i <= lt;++ i)q[st + i - 1] = lq[i];
    for(int i = 1;i <= rt;++ i)q[st + lt + i - 1] = rq[i];
    solve(l , mid , st , st + lt - 1);
    solve(mid + 1 , r , st + lt , ed);
    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",&a[i]);
        q[++ t].op = 0;
        q[t].l = i;
        q[t].k = a[i];
    }
    for(int i = 1;i <= m;++ i) {
        ++ t;
        q[t].op = i;
        scanf("%d%d%d",&q[t].l,&q[t].r,&q[t].k);
    }
    solve(-INF , INF , 1 , t);
    for(int i = 1;i <= m;++ i) {
        printf("%d\n",ans[i]);
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}