首页 > 代码库 > HDU2665_Kth number

HDU2665_Kth number

2024-07-13 13:09:46   224人阅读

给一个数组，求区间[l,r]中第k大的数。

今天被各种数据结构虐爆了，自己还是需要学习一下函数式线段树的，这个东西好像还挺常用。

函数式线段树的思想是这样的，对于每个时间状态，我们都建立一颗线段树，查询两个状态在某个区间的差的话，我们只要找到两个状态分别对应的点相减即可。

由于每次我使用线段树更新的时候，一路向下，所以我所涉及的更新的节点数量也只有log个，为了不改变原来的状态，可以选择新建这些节点。

这样所有的节点数量也不会超过n*log()个了。

对于此题，按照数组的顺序从左到右依次加入到线段树中，对于每个数组的位置都建立了一颗线段树，那么查找对于区间[l,r]的数字个数，我们只需要沿着两树的根节点一直往下面判断就可以了，每次判断两颗数的左二子数量相差是否大于K即可，也就是对于当前选择左走还是右走了，最终到达的点就是要找的那个第K大值了。

第一次使用 unique()和lower_bound()，内牛满面啊。 T_T !!!!! 

 

 

召唤代码君：

 

 

#include <iostream>#include <cstring>#include <cstdio>#include <algorithm>#define maxn 22222222using namespace std;int L[maxn],R[maxn],sum[maxn];int N,n,m,T;int a[maxn],lisan[maxn],b[maxn],cnt;void build(int l,int r,int& p){    p=++N; sum[p]=0;    if (l==r) return;    int mid=(l+r)>>1;    build(l,mid,L[p]);    build(mid+1,r,R[p]);}void update(int pre,int& p,int l,int r,int x){    p=++N;    L[p]=L[pre],R[p]=R[pre],sum[p]=sum[pre]+1;    if (l==r) return;    int mid=(l+r)>>1;    if (x<=mid) update(L[pre],L[p],l,mid,x);        else update(R[pre],R[p],mid+1,r,x);}int query(int u,int v,int l,int r,int k){    if (l==r) return l;    int mid=(l+r)>>1,num=sum[L[v]]-sum[L[u]];    if (num>=k) return query(L[u],L[v],l,mid,k);        else return query(R[u],R[v],mid+1,r,k-num);}int main(){    scanf("%d",&T);    while (T--)    {        scanf("%d%d",&n,&m);        N=0;        for (int i=1; i<=n; i++) scanf("%d",&a[i]),lisan[i]=a[i];        sort(lisan+1,lisan+1+n);        cnt=unique(lisan+1,lisan+1+n)-lisan-1;        build(1,cnt,b[0]);        for (int i=1; i<=n; i++)        {            int tmp=lower_bound(lisan+1,lisan+1+cnt,a[i])-lisan;            update(b[i-1],b[i],1,cnt,tmp);        }        while (m--)        {            int l,r,k;            scanf("%d%d%d",&l,&r,&k);            int pos=query(b[l-1],b[r],1,cnt,k);            printf("%d\n",lisan[pos]);        }    }    return 0;}


联系
我们