HDU2665Kth number （主席树+离散）

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

InputThe first line is the number of the test cases.
For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.
The second line contains n integers, describe the sequence.
Each of following m lines contains three integers s, t, k.
[s, t] indicates the interval and k indicates the kth big number in interval [s, t]OutputFor each test case, output m lines. Each line contains the kth big number.Sample Input

1

10 1

1 4 2 3 5 6 7 8 9 0

1 3 2

Sample Output

注意：题目是求第k小，可能写错了还是怎么的。
个人觉得既学习了主席树，也同时对离散的认识也加强了吧，表示以前没有用过unique结合lower_bound来离散操作。
没有格外的插入操作，不需要init和memset。但是要记住加地址符。
从现在开始，代码格式要更加规范，比如符号两边加空格。
Persistent line tree ，我姑且函数起名PIT，如果知道了其英文名字再改过来。
每次查询时范围都是（1，sz）；和普通的线段树的区别是：普通线段树从root=1开始沿下走。而主席树是沿两个root向下走，走的方向是一样的。

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

using namespace std;

const int maxn=;

int a[maxn],b[maxn],T,n,sz,q,cnt,ql,qr,x;

int ch[maxn * ][],sum[maxn * ],rt[maxn * ];

struct PLTree

{

    void build(int& now,int l,int r)

    {

        now = ++ cnt;

        sum[now] = ;//ch[now][0],cnt[now][1]没必要跟新，后面sum会跟新。

        if(l == r) return ;

        int Mid = (l + r)>>;

        build(ch[now][],l,Mid);

        build(ch[now][],Mid + ,r);

    }

    void insert(int& now,int last,int l,int r,int pos)

    {

        now = ++ cnt;

        ch[now][]=ch[last][];//假设公共，不同的部分下面再跟新。

        ch[now][]=ch[last][];

        sum[now] = sum[last] + ;

        if(l == r) return ;

        int Mid = (l+r) >> ;

        if(pos <= Mid) insert(ch[now][],ch[last][],l,Mid,pos);

        else insert(ch[now][],ch[last][],Mid + ,r,pos);

    }

    int query(int ss,int tt,int l,int r,int k)

    {

         if(l == r) return l;//要位置 ，不是要值

         int Mid =(l + r) >> ,tmp = sum[ch[tt][]] - sum[ch[ss][]];//本身呢？

         if(k <= tmp) return query(ch[ss][],ch[tt][],l,Mid,k);

         else return query(ch[ss][],ch[tt][],Mid + ,r,k - tmp);

    }

    void work()

    {

        scanf("%d%d%d",&ql,&qr,&x);

        int ans = query(rt[ql - ],rt[qr],,sz,x);//注意这个范围是（1，sz），和建树的时候的长度一样。

        printf("%d\n",b[ans]);

    }

};

PLTree P;

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&q);

        for(int i = ; i <= n;i ++) scanf("%d",&a[i]) , b[i]=a[i];

        sort(b + ,b + n + );

        sz = unique(b + ,b + n + )-(b + );

        cnt=;

        P.build(rt[],,sz);

        for(int i = ;i <= n;i ++) a[i]=lower_bound(b + ,b + sz + ,a[i]) - b;//a现在是排名

        for(int i = ;i <= n;i ++) P.insert(rt[i],rt[i-],,sz,a[i]);

        while(q--)  P.work();

    }

    return ;

}

巴特西

HDU2665Kth number （主席树+离散）

最新文章

热门文章