hdu2665 主席树（可持久化线段树）

时间：2023-03-08 22:21:07

题意：给定一个数组，每次查询第l到r区间的第k大值

解法嘛，当然是主席树，主席树即可持久化线段树，什么叫可持久化呢，就是指能够访问历史版本的数据结构，那么对于某些只能离线处理的题目强制在线之后 ，可以通过在线处理操作

经过这题总算对可持久化线段树有了些了解，我们开始先建一颗空树，然后对于每次修改我们只会修改logn个点，我们可以新建logn个来避免每次都新建一颗线段树导致的爆空间，

对于这题来说我们线段树中维护的是这个区间的点的个数，插入的时候按权值大小插入，对于l到r我们可以通过1-r减去1-(l-1)来求出l到r的，对于第k大我们可以用求平衡树第k大的做法，每次查询节点个数看往左走还是往右走

#include<bits/stdc++.h>

#define fi first

#define se second

#define mp make_pair

#define pb push_back

#define pi acos(-1.0)

#define ll long long

#define mod 1000000007

#define C 0.5772156649

//#define ls l,m,rt<<1

//#define rs m+1,r,rt<<1|1

#define pii pair<int,int>

using namespace std;

const double g=10.0,eps=1e-;

const int N=+,maxn=+,inf=0x3f3f3f3f;

int a[N],b[N],tot,rt[N*],ls[N*],rs[N*],sum[N*];

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

{

    o=++tot;

    sum[o]=;

    if(l==r)return;

    int m=(l+r)>>;

    build(ls[o],l,m);

    build(rs[o],m+,r);

}

void update(int &o,int l,int r,int last,int p)

{

    o=++tot;

    ls[o]=ls[last];

    rs[o]=rs[last];

    sum[o]=sum[last]+;

    if(l==r)return ;

    int m=(l+r)>>;

    if(p<=m)update(ls[o],l,m,ls[last],p);

    else update(rs[o],m+,r,rs[last],p);

}

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

{

    if(l==r)return l;

    int m=(l+r)>>;

    int cnt=sum[ls[tt]]-sum[ls[ss]];

    if(x<=cnt)query(ls[ss],ls[tt],l,m,x);

    else query(rs[ss],rs[tt],m+,r,x-cnt);

}

void work(int sz)

{

    int ql,qr,x;

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

    int ans=query(rt[ql-],rt[qr],,sz,x);

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

}

void debug()

{

    puts("***********");

    for(int i=;i<=tot;i++)

        printf("%d %d %d\n",ls[i],rs[i],sum[i]);

    puts("***********");

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie();

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,q;

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

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

        sort(b+,b+n+);

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

        tot=;

        build(rt[],,sz);

      //  debug();

        for(int i=;i<=n;i++)a[i]=lower_bound(b+,b++sz,a[i])-b;

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

       // debug();

        while(q--)work(sz);

    }

    return ;

}

/********************

1

4 2

4 1 3 2

2 3 2

********************/

相关文章