GoldenPotato137的小屋

GoldenPotato137的小屋
一名HITer/LLer/ACMer的个人博客
  1. 首页
  2. 数据结构
  3. 主席树
  4. 正文

[Luogu P3567] [POI2014]KUR-Couriers

2019年3月7日 878点热度 0人点赞 0条评论

题面

洛谷P3567


Solution

大水题啊,真没什么好讲的
我们考虑建一颗权值主席树,从左往右逐个插入。因为个数满足可减性,因此我们可以很方便的“扣”出$[L,R]$区间构成的主席树。接下来只需要在树上二分看一下有没有出现次数超过$K$的即可。
时间复杂度$O(nlogn)$
就酱,这题就被我们切掉啦︿( ̄︶ ̄)︿


Solution

#include<iostream>
#include<cstdio>
using namespace std;
const int N=500000+100;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct SegmentTree
{
    #define mid ((now_l+now_r)>>1)
    static const int M=25*N;
    int size[M],son[M][2],to;
    inline void update(int now)
    {
        size[now]=size[son[now][0]]+size[son[now][1]];
    }
    void Add(int now,int pre,int x,int now_l,int now_r)
    {
        if(now_l==now_r)
        {
            size[now]=size[pre]+1;
            return;
        }
        if(x<=mid)
        {
            son[now][1]=son[pre][1];
            Add(son[now][0]=++to,son[pre][0],x,now_l,mid);
        }
        else
        {
            son[now][0]=son[pre][0];
            Add(son[now][1]=++to,son[pre][1],x,mid+1,now_r);
        }
        update(now);
    }
    int Query(int now,int pre,int x,int now_l,int now_r)
    {
        if(now_l==now_r)
            return now_l;
        if(size[son[now][0]]-size[son[pre][0]]>=x)
            return Query(son[now][0],son[pre][0],x,now_l,mid);
        else if(size[son[now][1]]-size[son[pre][1]]>=x)
            return Query(son[now][1],son[pre][1],x,mid+1,now_r);
        return 0;
    }
    #undef mid
}sgt;
int root[N],n,m;
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
    {
        int tmp=read();
        sgt.Add(root[i]=++sgt.to,root[i-1],tmp,1,n);
    }
    for(int i=1;i<=m;i++)
    {
        int l=read(),r=read(),mid=(r-l+1)/2+1;
        printf("%d\n",sgt.Query(root[r],root[l-1],mid,1,n));
    }
    return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: 数据结构
最后更新:2019年3月7日

GoldenPotato137

LLer/ACMer/HITer/数院菜鸡/ECS折磨中

点赞
< 上一篇
下一篇 >

文章评论

取消回复

GoldenPotato137

LLer/ACMer/HITer/数院菜鸡/ECS折磨中

COPYRIGHT © 2022 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

桂ICP备20002051号