[HDU2665]Kth number (主席树)

发布于 2018-01-26  95 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU2665]Kth number (主席树)

Description

Give you a sequence and ask you the kth big number of a inteval.

Http

HDU

Tag

主席树

题目大意

求区间第\(K\)大

解决思路

主席树练手题。
相当于建立出\(n\)棵权值线段树,第\(i\)棵权值线段树保存的是前\(i\)个点的信息,那么类似与前缀和的思想,求\([l,r]\)的线段树就用第\(r\)棵线段树减去第\(l\)棵线段树,在这课作差得到的线段树上查询即可。而主席树就是利用已知信息节约空间。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100110;
const int inf=2147483647;

class SegmentData
{
public:
    int ls,rs;//左右儿子
    int sum;
};

int n,m;
int nodecnt=0;
SegmentData S[maxN*20];
int root[maxN];//保存根节点
int Arr[maxN],Brr[maxN];

void Build(int &now,int l,int r);
void Update(int &now,int l,int r,int num);
int Query(int now1,int now2,int l,int r,int kth);

int main()
{
    int T;scanf("%d",&T);
    while (T--)
    {
        nodecnt=0;
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) scanf("%d",&Arr[i]),Brr[i]=Arr[i];
        sort(&Brr[1],&Brr[n+1]);//读进来后先离散化
        for (int i=1;i<=n;i++) Arr[i]=lower_bound(&Brr[1],&Brr[n+1],Arr[i])-Brr;
        Build(root[0],1,n);//初始化
        for (int i=1;i<=n;i++) root[i]=root[i-1],Update(root[i],1,n,Arr[i]);//构造n棵主席树
        while (m--)
        {
            int l,r,kth;scanf("%d%d%d",&l,&r,&kth);//查询第K大
            printf("%d\n",Brr[Query(root[l-1],root[r],1,n,kth)]);
        }
    }
    return 0;
}

void Build(int &now,int l,int r)
{
    now=++nodecnt;
    if (l==r) return;
    int mid=(l+r)/2;
    Build(S[now].ls,l,mid);
    Build(S[now].rs,mid+1,r);
    return;
}

void Update(int &now,int l,int r,int num)
{
    S[++nodecnt]=S[now];
    S[now=nodecnt].sum++;
    if (l==r) return;
    int mid=(l+r)/2;
    if (num<=mid) Update(S[now].ls,l,mid,num);
    else Update(S[now].rs,mid+1,r,num);
    return;
}

int Query(int now1,int now2,int l,int r,int kth)
{
    if (l==r) return l;
    int lsize=S[S[now2].ls].sum-S[S[now1].ls].sum;
    int mid=(l+r)/2;
    if (lsize>=kth) return Query(S[now1].ls,S[now2].ls,l,mid,kth);
    else return Query(S[now1].rs,S[now2].rs,mid+1,r,kth-lsize);
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[HDU2665]Kth number (主席树)


HNCJ OIer