cf1076g

chenxia25 · 2021-08-03 20:52:21 · 题解

虽然是个 *3000 的题，但感觉也不是很 nb 的亚子嗷（

首先发现这字里行间都写着 ICG 三个大字，感觉很舒服。

可能的状态只有可能是这样的：某个后缀原封不动，然后这个后缀的上一个位置 i 的值随便（j\in[0,a_i)），设其 SG 值为 s_{i,j}。这个题不涉及 ICG 的和，只需要考虑非零性。考虑转移，显然 s_{i,j}=\bigvee\limits_{k=i+1}^{i+m}\lnot s_{k,a_k-1}\lor\lnot s_{i,j-1}，后面一项如果满足 j>0 的话。容易发现一个事实：把 i 作阶段的话，每个阶段过后只可能关心 s_{i,a_i-1}。考虑只算这个东西。容易发现针对某个阶段，若那个 bigvee 里面有 1 的话肯定是 1 了；否则 j=0\sim a_i-1 是 0 1 0 1 这样有周期性的，s_{i,a_i-1}=1 当且仅当 a_i 是偶数。那么 a_i 只关心奇偶性，好家伙这幌子打得漂亮。

那考虑暴力算法：就从右往左对 t_i=s_{i,a_i-1} 递推就行了。

很自然的想到，维护一个最近 m 个位置的 t 值的向量，如果这个递推关系可以写成一个有结合律的变换那就可以线段树维护区间复合了。首先想到的是线性变换，那考虑能不能实现逻辑或的表达？这玩意 \bmod 2 意义下，只能表示异或，那么或能不能用异或表达出来？很遗憾，不能。一个简短的证明是，异或满足交换律结合律消去律，再怎么组合都只能是一堆人的异或再选择性地取反。

再想想就发现 wsbl。这个状态数这么少，只有 2^m，可以暴力存啊，这是最原始的变换——数组映射啊。。。。。那复合就可以 trivial 地 \mathrm O(2^m)。然后区间查询可以的，区间修改就打懒标记的话怎么迅速区间取反呢，实时维护一个反的复合做备用然后取反的时候 swap 即可。复杂度 \mathrm O(q2^m\log n)，有点危。再稍微想一下发现合法状态的向量里面最多有一个 0，那只有 m+1 种，复杂度 \mathrm O(qm\log n)（早就预料到是这个复杂度）。

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m,qu;
bool a[N];
struct trans{
    int to[6];
    int &operator[](int x){return to[x];}
    trans(){for(int i=0;i<6;i++)to[i]=i;}
    friend trans operator*(trans x,trans y){
        trans z;
        for(int i=0;i<6;i++)z[i]=x[y[i]];
        return z;
    }
};
struct segtree{
    struct node{trans t,t0;bool lz;}nd[N<<2];
    #define t(p) nd[p].t
    #define t0(p) nd[p].t0
    #define lz(p) nd[p].lz
    void sprup(int p){
        t(p)=t(p<<1)*t(p<<1|1);
        t0(p)=t0(p<<1)*t0(p<<1|1);
    }
    void bld(int l=1,int r=n,int p=1){
        lz(p)=0;
        if(l==r){
            trans &t=t(p),&t0=t0(p);
            for(int i=1;i<m;i++)t[i]=t0[i]=i+1;t[m]=t0[m]=0;
            t[0]=0,t0[0]=1;
            if(a[l])swap(t,t0);
            return;
        }
        int mid=l+r>>1;
        bld(l,mid,p<<1),bld(mid+1,r,p<<1|1);
        sprup(p);
    }
    void init(){
        bld();
    }
    void sprdwn(int p){
        if(lz(p)){
            swap(t(p<<1),t0(p<<1)),lz(p<<1)^=1;
            swap(t(p<<1|1),t0(p<<1|1)),lz(p<<1|1)^=1;
            lz(p)=0;
        }
    }
    void flip(int l,int r,int p=1,int tl=1,int tr=n){
        if(l<=tl&&r>=tr)return swap(t(p),t0(p)),lz(p)^=1,void();
        sprdwn(p);
        int mid=tl+tr>>1;
        if(l<=mid)flip(l,r,p<<1,tl,mid);
        if(r>mid)flip(l,r,p<<1|1,mid+1,tr);
        sprup(p);
    }
    trans ask(int l,int r,int p=1,int tl=1,int tr=n){
        if(l<=tl&&r>=tr)return t(p);
        sprdwn(p);
        int mid=tl+tr>>1;trans res;
        if(l<=mid)res=res*ask(l,r,p<<1,tl,mid);
        if(r>mid)res=res*ask(l,r,p<<1|1,mid+1,tr);
        return res;
    }
}segt;
int main(){
    cin>>n>>m>>qu;
    for(int i=1;i<=n;i++){
        long long x;
        scanf("%lld",&x);
        a[i]=x&1;
    }
    segt.init();
    while(qu--){
        int tp,l,r;
        scanf("%d%d%d",&tp,&l,&r);
        if(tp==1){
            long long x;
            scanf("%lld",&x);
            if(!(x&1))continue;
            segt.flip(l,r);
        }
        else printf("%d\n",segt.ask(l,r)[0]==1?2:1);
    }
    return 0;
}