题解 P3567 【[POI2014]KUR-Couriers】

panyf · 2020-01-22 23:06:46 · 题解

和其他题解不同的方法

前置知识：摩尔投票法，不会的左转P2397学习一下。

摩尔投票是可以合并的，可以用线段树维护。我们只需维护区间内可能的众数和票数即可，合并时分类讨论一下。注意选出的数还需验证其出现次数是否达到区间长度的一半，可以用动态开点线段树维护每个数的出现次数。

本题还有增强版P3765，不过毒瘤卡空间，动态开点线段树要写空间回收。

详细注释代码如下：

#include<cstdio>
struct T1{
    int v,s;//v是选出的数，s为票数
}t[2000009];
struct T2{
    int l,r,v;//v为区间内该数出现次数
}s[10000009];
int u,v,id,p[500009],rt[500009];
void build(int k,int l,int r){
    if(l==r){
        t[k].v=p[l],t[k].s=1;
        return;
    }
    register int m=l+r>>1,a=k<<1,b=a|1;
    build(a,l,m),build(b,m+1,r);
    //以下为核心部分
    if(t[a].v==t[b].v)t[k].v=t[a].v,t[k].s=t[a].s+t[b].s;//众数相同，票数相加
    else if(t[a].s>t[b].s)t[k].v=t[a].v,t[k].s=t[a].s-t[b].s;//众数不同，取票数多的为众数，票数相减
    else t[k].v=t[b].v,t[k].s=t[b].s-t[a].s;
}
T1 qry(int k,int l,int r){//查询众数
    if(u<=l&&r<=v)return t[k];
    register int m=l+r>>1,a=k<<1,b=a|1;
    if(m>=v)return qry(a,l,m);
    if(u>m)return qry(b,m+1,r);
    register T1 x=qry(a,l,m),y=qry(b,m+1,r);
    if(x.v==y.v)x.s+=y.s;
    else if(x.s>y.s)x.s-=y.s;
    else x.v=y.v,x.s=y.s-x.s;
    return x;
}
void upd(int&k,int l,int r){//动态开点线段树插入
    if(!k)k=++id;
    ++s[k].v;
    if(l==r)return;
    register int m=l+r>>1;
    if(u<=m)upd(s[k].l,l,m);else upd(s[k].r,m+1,r);
}
int qnum(int k,int l,int r){//查询区间内某个数出现次数
    if(u<=l&&r<=v)return s[k].v;
    register int m=l+r>>1,z=0;
    if(u<=m)z=qnum(s[k].l,l,m);
    if(m<v)z+=qnum(s[k].r,m+1,r);
    return z;
}
int main(){
    register int n,m,i,j,k;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)scanf("%d",p+i),u=i,upd(rt[p[i]],1,n);
    build(1,1,n);
    while(m--){
        scanf("%d%d",&u,&v),j=qry(1,1,n).v;
        if((qnum(rt[j],1,n)<<1)>v-u+1)printf("%d\n",j);//出现次数超过一半再输出
        else puts("0");
    }
    return 0;
}