归并树模板

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) ((int)x.size())
#define clr(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define all(x) x.begin(),x.end()
typedef long long ll;
const int maxn=1e3+7;
const int INF=1e9+7;
int n,m,t;
int a[maxn];
int l,r,c;



//归并树模板 
/*
注意:    1.在build()之后需要将输入数组a[i] sort
        2.query(L,R,V) 返回在[L,R]区间内<=V的数的数量 
*/
vector<int> dat[maxn<<2];
void pushup(int rt){
    merge(all(dat[rt<<1]),all(dat[rt<<1|1]),dat[rt].begin());
}
void build(int l=1,int r=n,int rt=1){
    dat[rt].clear();
    if(l==r)dat[rt].pb(a[l]);
    else{
        int m=(l+r)>>1;
        build(lson);
        build(rson);
        dat[rt].resize(r-l+1);
        pushup(rt);
    } 
}

//query 返回在[L,R]区间内小于等于v的数的数量 
int query(int L,int R,int v,int l=1,int r=n,int rt=1){
    if(L<=l&&r<=R)return upper_bound(all(dat[rt]),v)-dat[rt].begin();
    int m=(l+r)>>1;
    int res=0;
    if(L<=m)res+=query(L,R,v,lson);
    if(R>m)res+=query(L,R,v,rson);
    return res;
}
//返回第K小 
int get_k_min(int L,int R,int c){
    int l=1,r=n;
    while(l<r){
        int mid=(l+r)>>1;
        int res=query(L,R,a[mid]);
//        printf("res:%d mid:%d a[mid]:%d \n\n",res,mid,a[mid]);
        if(res<c)l=mid+1;
        else r=mid;
    }
    return a[r];
}
//返回第k大
int get_k_max(int L,int R,int c){
    return get_k_min(L,R,R-L+1-(c-1));
}

int main(){
#ifdef AC
freopen("data.txt","r",stdin);
#endif
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    build();
    scanf("%d",&m);
    sort(a+1,a+n+1);
    while(m--){
        scanf("%d%d%d",&l,&r,&c);
        printf("%d\n",get_k_max(l,r,c));
//        for(int i=l-1;i<r;i++)tmp[i-l+1]=a[i];
//        sort(tmp,tmp+r-l+1);
//        printf("%d\n",tmp[r-l+1-c]);
    }
    return 0;
}

文章作者: crazyX
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 crazyX !
评论
 上一篇
2017-06-26 重新开始 2017-06-26 重新开始
这一年的时间,发生了太多太多的事情,从脱单到恢复单身,从区域赛打铁拿铜到今年邀请赛夺金,从心理,从认知,可能是我这么多年来,跨度最大的一年。 看开了很多事情,也明白了什么才是自己真正应该坚持的,年轻真好,还有后悔的机会,虽然后悔也需要付出不
2017-06-26
下一篇 
生日快乐 生日快乐
悬弧令旦,元服既成。 ** 罄无不宜,以莫不兴。** ** 如冈如阜,如丘如陵。** ** 如川方至,以莫不增。** ** 如月之恒,如日之升。** ** 如山之韧,不骞不崩。** ** 俾尔多益,以莫不成。** 每天我都在12点之后睡去
2017-03-07
  目录