欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

主席树(可持久化线段树)

程序员文章站 2024-03-03 18:24:28
...

先开个坑,这个坑会补的。

简介

代码

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct pp
{
    int a,id;
}a[1000010];
struct node
{
    int l,r,val;
}t[4000010];
int n,m;
int root[1000010];
int tot,f[1000010];

int modify(int pre,int l,int r,int x)
{
    int now=++tot;
    if(l==r)
    {
        t[now].val=t[pre].val+1;
        t[now].l=t[now].r=0;
        return now;
    }
    else
    {
        int mid=l+r>>1;
        if(x<=mid)
        {
            t[now].r=t[pre].r;
            t[now].l=modify(t[pre].l,l,mid,x);
        }
        else
        {
            t[now].l=t[pre].l;
            t[now].r=modify(t[pre].r,mid+1,r,x);
        }
    }
    t[now].val=t[t[now].l].val+t[t[now].r].val;
    return now;
}

int query(int root1,int root2,int l,int r,int k)
{
    if(l==r)
    {
        return l;
    }
    int mid=l+r>>1;
    int suml=t[t[root2].l].val-t[t[root1].l].val;
    if(suml>=k)
      return query(t[root1].l,t[root2].l,l,mid,k);
    else return query(t[root1].r,t[root2].r,mid+1,r,k-suml);
}

bool comp(pp a,pp b)
{
    return a.a<b.a;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].a);
        a[i].id=i;
    }
    sort(a+1,a+n+1,comp);
    int num=0;
    for(int i=1;i<=n;i++)
    {
        f[a[i].id]=i;
    }
    for(int i=1;i<=n;i++)
      root[i]=modify(root[i-1],1,n,f[i]);
    for(int i=1;i<=m;i++)
    {
        int l,r,k;
        int ans=0;
        scanf("%d%d%d",&l,&r,&k);
        ans=query(root[l-1],root[r],1,n,k);
        printf("%d\n",a[ans]);
    }
    return 0;
}
相关标签: 主席树