求第区间第k大数 TLE归并树

题

给定N个正整数构成的序列，将对于指定的闭区间查询其区间内的第K小值。

输入：

第一行包含两个正整数N、M，分别表示序列的长度和查询的个数。

第二行包含N个正整数，表示这个序列各项的数字。

接下来M行每行包含三个整数

输出：

包含k行，每行1个正整数，依次表示每一次查询的结果

//这是一道主席树模板题，在这儿先埋个伏笔 -_-||

做法

归并树。

就是线段树，每个节点存储它的区间内的排序。

询问操作时二分答案 mid。

query时利用归并排序的思想，mid的rank就等于各区间的rank加起来，查rank用到一个upper_bound

说实话是个，，很暴力的做法，

vector 的 merge 操作很好用在这里能省好多代码。

代码

#include<bits/stdc++.h>
#define MAXN 200005
using namespace std;
int read(){
    int x=0,t=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')t=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*t;
}
int N,Q,l[MAXN],r[MAXN],a[MAXN],b[MAXN],siz;
vector <int> Node[MAXN*4]; 
void Build_tree(int k,int li,int ri){
    l[k]=li,r[k]=ri;    int mid=li+ri>>1;
    if(li==ri){Node[k].push_back(a[li]);return;}
    Build_tree(k<<1,li,mid);Build_tree(k<<1|1,mid+1,ri);
    Node[k].resize(ri-li+1);
　　//上面这行丢了全RE =_=
    merge(Node[k<<1].begin(),Node[k<<1].end(),Node[k<<1|1].begin(),Node[k<<1|1].end(),Node[k].begin()); 
　　//STLvector里的合并函数
}
int Query(int k,int li,int ri,int x){
    if(ri<l[k]||r[k]<li)return 0;
    if(li<=l[k]&&r[k]<=ri)return upper_bound(Node[k].begin(),Node[k].end(),x)-Node[k].begin();
    return Query(k<<1,li,ri,x)+Query(k<<1|1,li,ri,x); 
　　//查询x的rank,归并排序思想↑
}
int main()
{
    N=read(),Q=read();
    for(int i=1;i<=N;i++)a[i]=b[i]=read();
    Build_tree(1,1,N);
    sort(b+1,b+N+1);siz=unique(b+1,b+N+1)-b-1;
    //存了一个b数组 排了序,后面要在这个有序序列里面二分枚举、找答案
　　 while(Q--){
        int L=read(),R=read(),rank=read();
        int Left=1,Right=siz;
        while(Left<=Right){
            int mid=Left+Right>>1;
            if(Query(1,L,R,b[mid])>=rank)Right=mid-1;
            else Left=mid+1; 
        }
　　　　　//二分时等于号、+1、-1的问题要看个人习惯处理好,不然死都不知道怎么死的...
        printf("%d
",b[Right+1]);
    }
    return 0;
}

推送

为了发展成音乐博客，写完代码顺便推歌。

写着题解的我正在听 -> http://music.163.com/song/475597495/?userid=476005944

Little Do You Know　　歌手：Campsite Dream