285484026

K-th Number 整体二分
K-th Number区间第K大,方法有很多可以用主席树,然后这几天学习了新姿势使用整体二分。整体二分板题#inc...
扫描右侧二维码阅读全文
13
2019/07

K-th Number 整体二分

K-th Number
区间第K大,方法有很多可以用主席树,然后这几天学习了新姿势使用整体二分。整体二分板题

#include <bits/stdc++.h>

const int MAXN = 500000;

using namespace std;

int n,m,top,cnt;
int A[MAXN],H[MAXN],C[MAXN],ans[MAXN];

struct node{
    int l,r,k,id;
}Q[MAXN],Tl[MAXN],Tr[MAXN];

inline void init(){
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;i++){
        scanf("%d",&A[i]);
        H[++top] = A[i];
    }

    sort(H+1,H+1+top);
    top = unique(H+1,H+1+top) - H;
    top--;

    for(int i = 1;i <= n;i++) {//修改
        Q[++cnt].l = i;
        Q[cnt].r = lower_bound(H+1,H+1+top,A[i]) - H;
        Q[cnt].id = 0;
    }
    
    for(int i = 1;i <= m;i++){//查询
        cnt++;
        scanf("%d %d %d",&Q[cnt].l,&Q[cnt].r,&Q[cnt].k);
        Q[cnt].id = i;
    }
}

inline int lowbit(int x){return x & -x;}

inline void add(int x,int d){
    for(;x <= top;x += lowbit(x)) C[x] += d;
}

inline int sum(int x){
    int ret = 0;
    for(;x;x -= lowbit(x)) ret += C[x];
    return ret;
}

inline 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].id)
                ans[Q[i].id] = H[L];
        return;
    }
    int lc,rc;
    lc = rc = 0;
    int M = (L + R) >> 1;
    for(int i = st;i <= ed;i++){
        if(Q[i].id == 0){
            if(Q[i].r <= M) add(Q[i].l,1),Tl[++lc] = Q[i];
            else Tr[++rc] = Q[i];
        }
        else {
            int    x = sum(Q[i].r) - sum(Q[i].l-1);
            if(Q[i].k <= x) Tl[++lc] = Q[i];
            else Q[i].k -= x,Tr[++rc] = Q[i];
        }
    }

    for(int i = ed;i >= st;i--)
        if(Q[i].r <= M && !Q[i].id)
            add(Q[i].l,-1);
    
    for(int i = 1;i <= lc;i++) Q[st+i-1] = Tl[i];
    for(int i = 1;i <= rc;i++) Q[st+lc+i-1] = Tr[i];
    solve(L,M,st,st+lc-1);
    solve(M+1,R,st+lc,ed);
}

int main()
{

    init();
    solve(1,top,1,cnt);
    for(int i = 1;i <= m;i++)
        printf("%d\n",ans[i]);
    return 0;
}
Last modification:July 13th, 2019 at 10:01 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment