P7261 题解

· · 题解

蒟蒻依旧想写丰富的开头，可是没有能力。

update 2024.3.21 重新提交以去除旧博客分类。

update 2024.1.20

  1. 去除了错误的算法描述，重构了对根号分治的分析。

  2. 微调了代码。

update 2024.1.1 ：

  1. 微调了讲解和代码，因为此题块长取 2000 虽然实际运行快但复杂度不正确，可以被 hack。
  2. 修改了复杂度说明，因为查询区间大小的上界应为 2 倍块长。

题目传送门

加强版及双倍经验

MnZn 做完题发现自己的做法（根号分治）与其他人（至少已有题解）不同，于是有了这篇。

对于这道题，先考虑暴力，发现有两种做法：（这两种暴力的顺序只是为了接下来的讨论。）

  1. 开桶暴力统计 [l,r] 区间内每种数出现次数，再暴力扫统计答案。

  2. 给每个数维护出现次数前缀和，这样就能 \Theta(1) 统计一个数在区间内的出现次数，再暴力扫一遍所有数，统计答案。

可以看出，前一种慢主要是因为区间太长，后一种慢主要是因为统计的数太多。

那么我们可以根号分治平衡复杂度，在区间较短时直接用第一种暴力，区间长时则可能成为答案的在整个数列内出现次数较多，因此需要维护出现次数前缀和的数也就少了，可以第 2 种暴力。具体来说，令块长（临界?）为 b：

因此总复杂度为 \Theta(n\times(b+\frac{n}{b}))。

从数学角度来说，有基本不等式可知 2b+\frac{n}{b} \ge 2\sqrt{2b\times\frac{n}{b}}=2\sqrt{2n}。因此当 b=\sqrt{2n} 时达到最好复杂度 \Theta(n\sqrt{n})。

但实际实现中，我们发现这个算法的空间复杂度为 \Theta(n\times \frac{n}{b})=\Theta(\frac{n^2}{b})，因此也可将 b 稍微开大来防止爆内存。（这道题中 n\le 3\times 10^5，我用了 b=1000）。

代码：（码风炸裂）

#include<cstdio>
#include<cstring>
#include<bitset>
#include<vector>
#include<map>
using namespace std;
#define M 100001
#define N 300001
#define B 1000
int s[N/B+1][N],p[N/B];
int q[10001],a[N];
bool jc[10001];
int c[10001];
inline void read(int& x){
    static char c;
    while((c=getchar())<'0');
    x=c^'0';
    while((c=getchar())>='0')x=(x<<3)+(x<<1)+(c^'0');
}
int main(){
    int n,m,uke;
    read(n);
    read(uke);
    int top=0;
    for(int i=1;i<=n;i++){
        read(a[i]);
        c[a[i]]++;
    }
    for(int i=1;i<=uke;i++){
        if(c[i]>=B)p[++top]=i;
    }
    for(int i=1;i<=top;i++){
        for(int j=1;j<=n;j++){
            s[i][j]=s[i][j-1]+(a[j]==p[i]?1:0);
        }
    }
    int l,r;
    read(m);
    for(int ttt=0;ttt<m;ttt++){
        bool flag=0;
        read(l);
        read(r);
        if(r-l+1<=(B*2)){
            for(int i=l;i<=r;i++){
                q[a[i]]++;
            }
            for(int i=l;i<=r;i++){
                if((q[a[i]]<<1)>(r-l+1))printf("yes %d\n",a[i]),flag=1;
                q[a[i]]=0;
            }
            if(!flag)printf("no\n");
        }
        else{
            for(int i=1;i<=top;i++){
                if(((s[i][r]-s[i][l-1])<<1)>(r-l+1)){
                    printf("yes %d\n",p[i]);
                    flag=1;
                    break;
                }
            }
            if(!flag)printf("no\n");
        }
    }
    return 0;
}