Loading...

洛谷P1533 可怜的狗狗

check评论:0 条 remove_red_eye浏览量:407 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-22

我又来刷两倍经验题了

这题就是主席树的模板,一模一样

上代码:

#include <bits/stdc++.h>
using namespace std;
const int maxn=300001;
#define mid ((lf+rg)>>1)
int n,q,m,cnt=0;
int a[maxn],b[maxn],t[maxn];
int sum[maxn<<5],l[maxn<<5],r[maxn<<5];
int build(int lf,int rg)
{
    int rt=++cnt;
    sum[rt]=0;
    if(lf<rg)
    {
        l[rt]=build(lf,mid);
        r[rt]=build(mid+1,rg);
    }
    return rt;
}
int update(int pre,int lf,int rg,int x)
{
    int rt=++cnt;
    l[rt]=l[pre];
    r[rt]=r[pre];
    sum[rt]=sum[pre]+1;
    if(lf<rg)
    {
        if(x<=mid)
        {
            l[rt]=update(l[pre],lf,mid,x);
        }
        else
        {
            r[rt]=update(r[pre],mid+1,rg,x);
        }
    }
    return rt;
}
int query(int u,int v,int lf,int rg,int k)
{
    if(lf>=rg)
    {
        return lf;
    }
    int x=sum[l[v]]-sum[l[u]];
    if(x>=k)
    {
        return query(l[u],l[v],lf,mid,k);
    }
    else
    {
        return query(r[u],r[v],mid+1,rg,k-x);
    }
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int m=unique(b+1,b+n+1)-b-1;
    t[0]=build(1,m);
    for(int i=1;i<=n;i++)
    {
        int tq=lower_bound(b+1,b+1+m,a[i])-b;
        t[i]=update(t[i-1],1,m,tq);
    } 
    for(int i=1;i<=q;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        int tq=query(t[x-1],t[y],1,m,z);
        printf("%d\n",b[tq]);
    }
    return 0;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名