题解 P7261 [COCI2009-2010#3] PATULJCI

iMya_nlgau · 2022-01-14 10:51:51 · 题解

因为这是一道黄题，所以不用主席树或者莫队这些算法。

我们对每种颜色开一个 vector 存下该颜色出现位置的下标，这样给定一个区间 [l,r] 和一个颜色 c 我们就可以在 vector 里二分求出 [l,r] 中 c 出现的次数，具体地，v[c] 表示颜色 c 下标的 vector，那么

upper_bound(v[c].begin(),v[c].end(),r)-lower_bound(v[c].begin(),v[c].end(),l);

就是 [l,r] 中 c 出现的次数。

然后再考虑，如果一个颜色 c 在长度为 k 的区间里出现了超过 \dfrac{k}{2} 次，那么我们在这个区间里随机 t 次，每次随机一个位置，遇不到 c 的概率小于 \dfrac{1}{2^t}，当 t 取 50 的时候这个概率大约是 10^{-15}，可以认为不可能发生。

所以对于每个询问 [l,r]，我们在 [l,r] 中随机 t 次，再判断每次随机到的颜色出现次数是否大于 \dfrac{r-l+1}{2} 即可。

时间复杂度 O(mt\log n)，t 为随机次数。t 取 20 的话我的代码是目前最优解。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;

inline int read(){
    int x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+(c^'0'),c=getchar();
    return x;
}

const int maxn=3e5+10;
const int maxm=1e4+10;

int n,c,m,a[maxn];
vector<int> v[maxm];

inline int query(int l,int r){
    for(int t=1;t<=50;t++){
        int p=l+rand()%(r-l+1);
        int res=upper_bound(v[a[p]].begin(),v[a[p]].end(),r)
            -lower_bound(v[a[p]].begin(),v[a[p]].end(),l);
        if(res>(r-l+1)/2) return a[p];
    }
    return -1;
}

int main(){
    srand((unsigned)time(NULL));

    n=read(),c=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),v[a[i]].push_back(i);

    for(int i=1;i<=c;i++) v[i].push_back(n+1);

    m=read();
    while(m--){
        int l=read(),r=read();
        int ans=query(l,r);
        if(~ans) printf("yes %d\n",ans);
        else puts("no");
    }

    return 0;
}