P4135 作诗题解

ctzm · 2025-05-19 16:40:29 · 题解

~~题目强制在线，不让你用莫队，你就不写了？你还真写分块啊？~~

这是一种非正解但可以过的做法，我命名为【并行莫队】。若要学习分块正解，请跳过本题解。

感谢 @little_grass_sage 赞助的看起来根本没啥用其实强得不得了的优化！

题意简述

给定 n 个不大于 c 的正整数 a_1 \dots a_n 和 m 组询问，每次问 [l,r] 中有多少个数出现正偶数次。询问强制在线。

数据范围：1\le n,c,m\le 10^5，1 \leq a_i \leq c，1 \leq l, r \leq n。

solution

先考虑如果不强制在线的做法：很显然可以用莫队算法解决。强制在线意味着我们不可以提前获取到所有的查询，只能按顺序处理，看上去莫队将退化到最坏 O(nm)。

回顾莫队算法思想，如果我们知道一个区间 [l,r] 的答案，又可以快速获取左或右端点变动 1 的区间的答案，那么就可以使用莫队离线排序查询，通过不断复用上一次的区间答案，在此基础上做次数足够少的变动来回答查询。

其实核心不在于“上一次”，而在于“这些区间我们有答案，以及维护答案的额外东西”。本题中“维护答案的额外东西”就是 cnt 数组维护每个数的出现次数，修改前删掉原本它的贡献（原本这个数出现次数是否是正偶数），然后修改，这个数出现次数加 1，修改后重新计算它的贡献（现在这个数出现次数是否是正偶数）。

在线用莫队解决的弊端在于我们只有一个区间答案以及维护答案的额外东西，如果不能离线查询，上一次和这一次的区间查询往往差距过大（变动次数过多，不可控），导致查询退化为 O(n)。那么我们多准备几个区间不就得了？当区间个数够多的时候，我们直接选择变动次数最少的一个区间去变动，从区间 [a,b] 变动到 [c,d] 的次数可 O(1) 计算，即为 |a-c| + |b-d|，这个变动次数直观感觉肯定不会太多。

我们直接初始时随机选取左端点 l_i，创造 s 个空区间 [l_i,l_i-1]，每次查询时，花费 O(s) 时间计算变动次数最小的区间，并进行莫队变动（这个变动是持久化的，也就是不会撤销，后面的查询也有可能以这个为基础继续变动）。

看起来这个“算法”思维很容易理解，复杂度感觉也很优秀，那么具体的表现呢？很遗憾，我们得到了 TLE 80pts。

怎么优化呢？考虑前 s 个查询，随机的 l_i 并不一定适配这些查询，比方说有查询 [10001,100000]，结果离这个查询最近的区间只有 [8001,8000]（实际可能不同，但由于随机比较离散，有个几百上千的差距都是正常的），于是我们干脆直接以这些查询的左端点作为初始区间的左端点，现场创造区间 [10001,10000]，在这个例子中能比纯随机省下 4000 变动，实际每个查询大概也能省下几千。

这个优化看似有限，取 s = 1000，先不说能省下几百，即使是 10000 也只有 10^7 运算的优化，洛谷机子快可能 0.1s 都不到，根本不起大作用，但却实实在在地成功让我们的做法通过本题！

那么，具体的时间复杂度呢？如果要卡掉的话估计难度很大，所以先不要脸地假装数据随机。这意味着 s 个区间也可以认为是随机的，变动次数本质就是曼哈顿距离。问题转化为：在 n \times n 方格上随机选 s 个点，然后再新增一个点，问这个点到所有 s 个点的任意一个曼哈顿距离的最小值期望是？这个是大约 O(\frac{n}{\sqrt s}) 的，找最小值是 O(s) 的，所以每个查询都是 O( \frac{n}{\sqrt s} + s) 的期望复杂度。容易证得，s 取 n^{2/3} 时理论达到最优 O(n^{2/3})，约等于 2154。但开 2154 个 cnt 数组肯定喜提 MLE，笔者这里取的是 s = 1000。由于除了空区间都有 l \le r，n \times n 方格其实只有约一半面积，这样取一半反而也更加合理。n,m 同阶，故总复杂度为 O(n^{5/3})。

这种算法由于开了很多个区间，这些是并行的参与到莫队，所以叫【并行莫队】。我个人的确想不到什么办法卡掉这种算法，但思想具有启发性，并且也过了，~~适宜我们这些不会分块的人民骗分~~，所以发出来，欢迎大家证明 / 证伪复杂度或者加 hack。

还有一点：为什么我们肯定这题数据随机？题目的加密强制在线方式如果想要特殊构造 hack 数据是非常简单的，如果想要特殊构造，当然也应该负责保证 L \le R。但题目居然跑出来说要交换，说明出题人根本没想这回事，明显保证数据随机！甚至样例 l=0 都跑出来了！

好了，就这样吧，代码：

const int s=1000;
int n,c,m,a[100010],L[1005],R[1005],cnt[1005][100010],ans[1005],lastans;
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cout.tie(0);
    cin>>n>>c>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int _=1;_<=m;_++){
        int l,r;
        cin>>l>>r;
        l=(l+lastans)%n+1;
        r=(r+lastans)%n+1;
        if(l>r)swap(l,r);
        int c=1;
        if(_<=s)c=_,L[_]=l,R[_]=L[_]-1;
        else for(int i=1;i<=s;i++)if(abs(l-L[i])+abs(r-R[i])<abs(l-L[c])+abs(r-R[c]))c=i;
        while(L[c]<l){
            if(cnt[c][a[L[c]]]&&cnt[c][a[L[c]]]%2==0)ans[c]--;
            cnt[c][a[L[c]]]--;
            if(cnt[c][a[L[c]]]&&cnt[c][a[L[c]]]%2==0)ans[c]++;
            L[c]++;
        }
        while(L[c]>l){
            L[c]--;
            if(cnt[c][a[L[c]]]&&cnt[c][a[L[c]]]%2==0)ans[c]--;
            cnt[c][a[L[c]]]++;
            if(cnt[c][a[L[c]]]&&cnt[c][a[L[c]]]%2==0)ans[c]++;
        }
        while(R[c]<r){
        R[c]++;
            if(cnt[c][a[R[c]]]&&cnt[c][a[R[c]]]%2==0)ans[c]--;
            cnt[c][a[R[c]]]++;
            if(cnt[c][a[R[c]]]&&cnt[c][a[R[c]]]%2==0)ans[c]++;
        }
        while(R[c]>r){
            if(cnt[c][a[R[c]]]&&cnt[c][a[R[c]]]%2==0)ans[c]--;
            cnt[c][a[R[c]]]--;
            if(cnt[c][a[R[c]]]&&cnt[c][a[R[c]]]%2==0)ans[c]++;
            R[c]--;
        }
        cout<<ans[c]<<'\n';
        lastans=ans[c];
    }

    return 0;
}

P4135 作诗 题解

题意简述

solution

P4135 作诗题解