P12846 [蓝桥杯 2025 国 A] 翻转硬币 题解

· · 题解

『隔一个翻一个？隔两个翻一个？这咋做？』

「你先别考虑那么多啊，你会做直接翻转和查询的吗？」

『有啥难度，不就是 P3870 的线段树大法吗。』

「答对咯，就是线段树。那你能详细说下线段树怎么处理吗？」

『这很简单吧，除去正常线段树要维护的内容，再额外维护一下该区间正面朝上的硬币个数。要翻转，就让当前的正面朝上硬币个数被区间长度减一遍，其他都是板子吧。但是……？』

「但是这道题目还有隔一个和隔两个对不对，可以理解为 2 个选一个、3 个选一个，以及前面的 1 个选一个。」

『哦……』

「2，3，1，余数，你想到了什么？」

『完了，该不是要维护 6 棵线段树啊？』

「对，就是 6 棵线段树。但是 6 是怎么得出来的呢？」

『6，不就是 2,3,1 三个数的最小公倍数嘛！毕竟你不可能全部分开处理，那就按照除以 6 的余数开 6 个线段树咯。』

「非常棒，那么下一个问题来了，你在维护的时候，需要处理哪些余数呢？」

『分类讨论一下吧。以 2 为周期的，那就是看 [x,y] 这段区间里有多少个除以 6 余数是 x \bmod 6、(x+2) \bmod 6、(x+4) \bmod 6 的位置，对它们都进行翻转。』

「对。之所以有三个不同余数，是因为这里只隔 2 个，并没隔 6 个。接下来呢？」

『同理，以 3 为周期的，就是看 [x,y] 这段区间里有多少个除以 6 余数是 x \bmod 6 和 (x+3) \bmod 6 的位置，去做翻转。』

「以及只剩下常规套路，全都翻转的那种，就每个余数遍历一遍就行啦！」

『对对。额，那么我还有最后一个问题，该如何快速确定某段区间中有哪些数的余数是某个值呢？』

「呀，这个应该是有标准数学公式的，不过我们可以用常数稍大一些的枚举法，枚举出起点终点就行了哦。从区间的左端点、右端点分别往中间靠拢嘛，余数不对就缩进嘛。」

『哦！我明白了。这样的常数也不算大呀，只有 6 呢。』

「到这里，这题基本就结束了吧，你听懂了吗？」

『听是听懂了，但是 Talk is cheap , show me your code .，代码快快放出来哇 > < 』

「当然会放代码咯。不过我事先说好，这代码写的有点乱，某些内容可能是兀余的，可读性不一定好，将就看吧。」

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
using namespace std;
const int N = 2e6+5;
int n,Q,a[N],bel[N];
struct SegTree{
    int up,a[N],s[N],t[N];
    int ls(int x){return (x<<1);}
    int rs(int x){return (x<<1|1);}
    void push_up(int x){s[x]=s[ls(x)]+s[rs(x)];return;}
    void build(int x,int l,int r){
        if(l==r){s[x]=a[l],t[x]=0;return;}
        int mid=(l+r)>>1;
        build(ls(x),l,mid);build(rs(x),mid+1,r);
        push_up(x);return;
    }
    void push_down(int x,int l,int r){
        if(!t[x])return;
        t[ls(x)]^=1,t[rs(x)]^=1;
        int mid=(l+r)>>1;
        s[ls(x)]=(mid-l+1)-s[ls(x)];
        s[rs(x)]=(r-mid)-s[rs(x)];
        t[x]=0;return;
    }
    void change(int x,int l,int r,int L,int R){
        if(r<L||R<l)return;
        if(L<=l&&r<=R){s[x]=(r-l+1)-s[x],t[x]^=1;return;}
        push_down(x,l,r);
        int mid=(l+r)>>1;
        change(ls(x),l,mid,L,R);
        change(rs(x),mid+1,r,L,R);
        push_up(x);return;
    }
    LL ask(int x,int l,int r,int L,int R){
        if(r<L||R<l)return 0;
        if(L<=l&&r<=R)return s[x];
        push_down(x,l,r);
        int mid=(l+r)>>1;
        return ask(ls(x),l,mid,L,R)+ask(rs(x),mid+1,r,L,R);
    }
}SegT[7];
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}

int main(){
    n=read(),Q=read();
    for(int i=1;i<=n;i++){
        int x=read();
        bel[i]=(!(i%6)?6:(i%6));
        SegT[bel[i]].a[++SegT[bel[i]].up]=x;
    }
    for(int i=1;i<=6;i++)
        SegT[i].up=n/i+((n%i)<=i),
        SegT[i].build(1,1,SegT[i].up);
    while(Q--){
        int opt=read(),x=read(),y=read();
        if(opt==1){
            int ys=(x%6);
            for(int c=1;c<=3;c++,ys=(ys+2)%6){
                int st=x;
                while(st%6!=ys&&st<=y)st++;
                if(st>y)continue;
                int ed=y;
                while(ed%6!=ys&&ed>st)ed--;
                if(!ys)ys=6;
                st=(st+5)/6,ed=(ed+5)/6;
                SegT[ys].change(1,1,SegT[ys].up,st,ed);
            }
        }else if(opt==2){
            int ys=(x%6);
            for(int c=1;c<=2;c++,ys=(ys+3)%6){
                int st=x;
                while(st%6!=ys&&st<=y)st++;
                if(st>y)continue;
                int ed=y;
                while(ed%6!=ys&&ed>st)ed--;
                if(!ys)ys=6;
                st=(st+5)/6,ed=(ed+5)/6;
                SegT[ys].change(1,1,SegT[ys].up,st,ed);
            }
        }else if(opt==3){
            int ys=(x%6);
            for(int c=1;c<=6;c++,ys=(ys+1)%6){
                int st=x;
                while(st%6!=ys&&st<=y)st++;
                if(st>y)continue;
                int ed=y;
                while(ed%6!=ys&&ed>st)ed--;
                if(!ys)ys=6;
                st=(st+5)/6,ed=(ed+5)/6;
                SegT[ys].change(1,1,SegT[ys].up,st,ed);
            }
        }else{
            int res=0,ys=(x%6);
            for(int c=1;c<=6;c++,ys=(ys+1)%6){
                int st=x;
                while(st%6!=ys&&st<=y)st++;
                if(st>y)continue;
                int ed=y;
                while(ed%6!=ys&&ed>st)ed--;
                if(!ys)ys=6;
                st=(st+5)/6,ed=(ed+5)/6;
                res+=SegT[ys].ask(1,1,SegT[ys].up,st,ed);
            }cout<<res<<"\n";
        }
    }
    return 0;
}

『你这下面几个部分都是复制粘贴的呀！就差一个数字呢！我可以帮你压得短短的！』

「我知道啦，但是看到这里还不点赞的朋友们真的很残忍哦……麻烦留个赞吧，求求了喵！」