首页
登录 | 注册

HDU-2665 Kth number (可持久化线段树)

题目链接

HDU-2665 Kth number

题目大意

给定长度为n的序列,有m次询问,每次询问区间[l,r]内的第k小数是多少?

Sample Input

1
10 1
1 4 2 3 5 6 7 8 9 0
1 3 2

Sample Output

2

思路

区间第k大问题一直不会,先学了一下划分树,虽然跑的很快,但是更改查询区间部分有点绕,容易写错,而且只能用于不修改的区间第k大问题,估计比赛中不会用到。

又学了一下可持久化线段树,发现线段树的叶子结点就是权值,而不是通常的区间。
建树时,对[1,i]的所有区间都建立一棵权值线段树,对应的线段树为root[i],这样在查询区间[l,r]时,线段树root[r]root[l1]就是区间[l,r]每个值出现的次数,然后很容易就能查询到区间第k大。

建树时,由于每次只有根到叶子结点的一条路径上的log(n)个结点会被改变,其他结点不变,所以每次只增加改变的结点,其他结点指向上一颗树的相应结点即可,空间复杂度为nlogn

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

/*
可持久化线段树 -- 查询区间第k小【查询区间第k大,即查询区间第 r-l+1-k+1=r-l+2-k 小】

初始化:a[1..n]为原序列,sorted[1..n]为原序列的备份,然后调用build就行
hash后的值为当前数第一次出现的下标,所以存在部分下标无对应的值,但相对简单
*/
const int MAXN=100007;
const int LOGMAXN=19;//100 000个数用19就够了

//可持久化线段树是权值线段树,即区间就是权值,而与原序列的区间无关
//第i棵数是原序列区间[1,i]建立的权值线段树
struct Node {//为防止MLE,线段树结点不再保存区间端点,而是动态求得
    int lson,rson;
    int sum;//sum表示各权值出现次数之和
}tr[MAXN*LOGMAXN];

int n;
int a[MAXN],sorted[MAXN];//a[1..n]表示原序列,sorted[1..n]表示排序后的序列
int root[MAXN],cnt;//cnt表示当前已用的结点数

void inser(int &cur,int ori,int val,int l=1,int r=n) {//cur表示当前线段树的编号【调用是传入root[i]即可】,ori传入root[i-1]即可,val是权值
    cur=cnt++;//给当前结点分配一个新的结点
    tr[cur]=tr[ori];
    ++tr[cur].sum;//插入了val后,新结点sum+1
    if(l==r) {
        return ;
    }
    int mid=(l+r)>>1;
    if(val<=mid) {
        inser(tr[cur].lson,tr[ori].lson,val,l,mid);
    }
    else {
        inser(tr[cur].rson,tr[ori].rson,val,mid+1,r);
    }
}

int query(int L,int R,int k,int l=1,int r=n) {//L,R分别表示查询区间左右端点代表的线段树的下标【调用是传入root[LL-1],root[RR]即可】
    if(l==r) {
        return l;
    }
    int tmp=tr[tr[R].lson].sum - tr[tr[L].lson].sum,mid=(l+r)>>1;//计算查询区间内前一半权值出现的次数
    if(k<=tmp) {
        return query(tr[L].lson,tr[R].lson,k,l,mid);
    }
    return query(tr[L].rson,tr[R].rson,k-tmp,mid+1,r);
}

void build() {//初始化并建立可持久化线段树
    tr[0].lson=tr[0].rson=tr[0].sum=root[0]=0;//由于以后lson,rson,sum的值都不会更改(子结点还是自己),所以只用一个根结点就能表示一棵空数
    cnt=1;
    sort(sorted+1,sorted+1+n);
    for(int i=1;i<=n;++i) {
        inser(root[i],root[i-1],lower_bound(sorted+1,sorted+1+n,a[i])-sorted);//这样hash会有部分下标无对应的数,但相对简单
    }
}

int m,l,r,k;

int main() {
    int T;
    scanf("%d",&T);
    while(T-->0) {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i) {
            scanf("%d",a+i);
            sorted[i]=a[i];
        }
        build();
        while(m-->0) {
            scanf("%d%d%d",&l,&r,&k);
            printf("%d\n",sorted[query(root[l-1],root[r],k)]);//注意返回的是下标
        }
    }
    return 0;
}


2020 jeepxie.net webmaster#jeepxie.net
10 q. 0.009 s.
京ICP备10005923号