P7261 题解

· · 题解

题意

给出一个 n 个数的序列并询问 m 次，每次查询给定一个区间，问区间内是否有出现次数超过区间长度一半（向下取整）的数，如果有输出这个数。

算法分析

我们引入摩尔投票这一方法。

假设现在有 n 张选票选举一个候选人，保证其中有一位候选人的支持率严格大于 50%，请你找出这位候选人。显然，答案是唯一的，否则总支持率将大于 100%。

摩尔投票的过程就是维护每个时刻的票数最高的候选人和它所对的票数，在投票时，如果投给这个候选人，就票数加一，否则票数减一。特别的，如果票数减一前发现这位候选人的票数是 0 可以直接把当前票上的候选人做为新的票数最高候选人并把票数变成 1.

用 C++ 代码实现:

int m,cnt;
int n,x;
cin>>n;
for(int i=1;i<=n;++i){
    cin>>x;
    if(x==m) ++cnt;
    else if(cnt==0) m=x,cnt=1;
    else --cnt;
}
cout<<m;

为什么是对的？因为它在过程中相当于将不同候选人的票进行抵消，其中有一位票数大于一半的一定无法被完全消除，就成为了答案。

更进一步的，抵消的思想启示我们摩尔投票的结果有结合律，有交换律，因此可以使用数据结构维护，支持区间查询结合律信息。由于本蒟蒻不会猫树和 Sqrt Tree 只好使用线段树维护了。

最后思考一个问题，无解时怎么办？无解时摩尔投票的最终结果无法保证正确，所以我们要验证答案在区间内出现次数是否超过区间长度的一半。

我们用 c 个 vector 储存每一种颜色所有的下标，验证时在答案的 vector 中二分找到不大于区间右端点的最大值和不小于区间左端点的最小值。由于 vector 内存连续，可以用迭代器相减算出某段中的元素个数。

代码：

#include <bits/stdc++.h>
using namespace std;
namespace IO{//by cyffff
    int len=0;
    char ibuf[(1<<20)+1],*iS,*iT,out[(1<<26)+1];
    #ifdef ONLINE_JUDGE
    #define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<20)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
    #endif
    #ifndef ONLINE_JUDGE
    #define gh() getchar()
    #endif
    #define reg register
    inline int read(){
        reg char ch=gh();
        reg int x=0;
        reg char t=0;
        while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
        while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
        return t?-x:x;
    }
    inline void putc(char ch){
        out[len++]=ch;
    }
    template<class T>
    inline void write(T x){
        if(x<0)putc('-'),x=-x;
        if(x>9)write(x/10);
        out[len++]=x%10+48;
    }
    inline void flush(){
        fwrite(out,1,len,stdout);
        len=0;
    }
}
using IO::read;
using IO::write;
using IO::flush;
using IO::putc;
int n,c,m;
const int maxn=3e5+5;
int a[maxn];
struct node{
    int m,cnt;
}trr[maxn<<2];
inline void merge(node &a,node &b){
    if(a.m==b.m){
        a.cnt+=b.cnt;
    }else{
        if(a.cnt>b.cnt) a.cnt-=b.cnt;
        else{
            a.m=b.m;
            a.cnt=b.cnt-a.cnt;
        }
    }
}
#define ls (p<<1)
#define rs (ls|1)
void build(int p,int l,int r){
    if(l==r){
        trr[p]=node{a[l],1};
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    trr[p]=trr[ls];
    merge(trr[p],trr[rs]);
}
node res;
void qry(int p,int l,int r,int st,int ed){
    if(l<=st&&ed<=r) merge(res,trr[p]);
    else{
        int mid=(st+ed)>>1;
        if(l<=mid) qry(ls,l,r,st,mid);
        if(mid<r) qry(rs,l,r,mid+1,ed); 
    }
}
vector<int> v[10001];
int l,r;
int main(){
    n=read(),c=read();
    for(int i=1;i<=n;++i){
        a[i]=read();
        v[a[i]].emplace_back(i);
    }
    build(1,1,n);
    m=read();
    while(m--){
        l=read(),r=read();
        res=node{0,0};
        qry(1,l,r,1,n);
        if(upper_bound(v[res.m].begin(),v[res.m].end(),r)-lower_bound(v[res.m].begin(),v[res.m].end(),l)<=((r-l+1)>>1)) putc('n'),putc('o');
        else putc('y'),putc('e'),putc('s'),putc(' '),write(res.m);
        putc('\n');
    }
    flush();
}

说句闲话：蒟蒻的 zkw 线段树太丑了没有放上来，zkw 线段树写法爆杀随机化取得目前最优解。