题解：B4106 [CSP-X2024 山东] 翻硬币

· · 题解

全场最劣解祭。

题意

给定一个初始为 0 的序列，每次可以将它的一个区间 01 翻转，问这个区间的最终结果。

思路

容易发现一个点被翻奇数次就会变成 1，翻偶数次就会变成 0。所以我们只需要统计每个点被翻转的次数。

每次翻转一个区间，可以用区间加，但是线段树的代码过于复杂，会吓到小学组的孩子们，我选择使用优化后的暴力。

我们可以给这个区间分成若干个长度为 \sqrt{n} 的块。对于每次修改的区间可以被分为三部分：中间的整块，左边不足一块的和右边不足一块的部分。

对于中间的整块，给每一个块打上一个加 1 的标记，对于两遍不足一块的部分，直接暴力加就好了。发现中间块的个数不会超过 \sqrt{n}，两遍的长度分别不会超过 \sqrt{n}，所以总体一次修改就是 O(\sqrt{n}) 的。

查询的时候，只需要将每个点所在块的加 1 标记数和暴力加的次数加起来即可。

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,pos[200050],len,a[200005],b[500],L[500],R[500];//a是每个数暴力加的次数，b是每个块的标记 
void add(int l,int r){
    int p=pos[l],q=pos[r];
    if(p==q){//特判修改端点在一个块的情况 
        for(int i=l;i<=r;i++) a[i]++;
        return;
    }
    for(int i=l;i<=R[p];i++) a[i]++;//处理左边散块 
    for(int i=L[q];i<=r;i++) a[i]++; //处理右边散块 
    for(int i=p+1;i<=q-1;i++) b[i]++; //处理整块 
}
int main(){
    cin>>n>>m;
    len=sqrt(n);
    for(int i=1;i<=len;i++){
        L[i]=(i-1)*sqrt(n)+1;
        R[i]=i*sqrt(n);
    }
    if(R[len]<n){
        len++;
        L[len]=R[len-1]+1,R[len]=n;
    }
    for(int i=1;i<=len;i++)
        for(int j=L[i];j<=R[i];j++)
            pos[j]=i;
    //以上是分块预处理，维护每个块左、右端点，每个点属于哪个块 
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        add(x,y);
    }
    for(int i=1;i<=n;i++) {
        int val=a[i]+b[pos[i]];
        cout<<(val&1);
    }
    return 0;
}

这份代码以 O(n\sqrt n) 的时间复杂度成功地成为了本题 AC 记录中最慢的一个，10 个点共耗时 600ms。