题解：P13905 「KFCOI Round #2」宿命

Shunpower · 2025-08-29 19:13:21 · 题解

如果你做过 CF1515H 等一类区间位运算的数据结构典题，那么做这种题会好处理一点。当然，就算没做过也不会遇到什么特别的困难。

考虑 \mathcal O(q\log n\log V+n\log V) 的拆位做法是简单的，只是需要逐位处理优化空间复杂度。但是被 LK 卡成了 20 分，太邪恶了。

考虑怎么 1log。不妨先看一个弱化的问题怎么 1log，也就是本题的 Subtask 5：

给定一个序列 \{a_n\}，支持区间按位与、按位或、按位异或一个数 x，查询区间按位与、按位或、按位异或。

考虑使用线段树维护区间的位运算值。问题在于我们怎么打标记。

如果我们沿用拆位的思路，可以发现实际上每个标记是一个 \{0,1\}^{63}\to \{0,1\}^{63} 的映射。换句话说，每个区间上的标记实际上是一个二维数组 f_{i,0/1}=0/1，表示如果某个数的第 i 位是 0 或 1，那么标记传下去它就会变成 f_{i,0/1}。

我们显然可以用两个 63 进制数 F_0,F_1 维护标记。F_0 的第 i 位就是刚刚说的 f_{i,0}，F_1 同理。

合并标记是简单的，我们考虑左标记 F_0,F_1，把右标记 G_0,G_1 乘进去：F_0 中为 1 的位套上 G_1，为 0 的位套上 G_0；F_1 同理。这可以用位运算快速完成：

friend Tag operator*(const Tag &p,const Tag q){
    ull h0=((~p.f0)&q.f0)|(p.f0&q.f1);
    ull h1=((~p.f1)&q.f0)|(p.f1&q.f1);
    return {h0,h1};
}

然后考虑标记和信息的合并。这个也只需把每种位运算，每一位的 0,1 拆出来讨论一下形式就好了。以按位与为例：

• 区间按位与为 0 的位，证明这个区间的数当中这一位至少有一个 0。如果有 0 有 1，那么当且仅当 F_0,F_1 这一位都为 1 可以把区间按位与这一位也搓成 1；如果全 0（可以用按位或的取反来判定），那么当且仅当 F_0 这一位为 1 可以把区间按位与这一位也搓成 1。
• 区间按位与为 1 的位，证明这个区间的数这一位都是 1。那么当且仅当 F_1 这一位为 1 可以把区间按位与这一位也搓成 1。

以此类推，标记乘信息写出来就长这样：

friend Info operator*(const Info &p,const Tag q){
    ull both=q.f0&q.f1;
    ull nand=both|(q.f1&p.vand)|(q.f0&~p.vor);//这条是按位与
    ull nor=both|(q.f1&p.vor)|(q.f0&~p.vand);
    ull nxor=((p.len&1)?q.f0:0ull)^(p.vxor&(q.f1^q.f0));
    return {nand,nor,nxor,p.len};
}

在理解了标记的含义之后，根据修改设计标记是不难的，这里不赘述了。写一棵线段树即可通过 Subtask 5。

然后考虑回到原问题。可以发现，我们实际上是可以把修改操作给弄成位运算全部相同的：比如选一堆位置出来按位与，那么对于这部分位置确实是在与 x 中的对应位，但我们也可以理解成是整个数在与，只是说其他位置在与 1。

于是我们把不对应的位置设置为这种位运算的单位元（与是 1，或和异或是 0），这样就把一个所谓“自定义运算”的修改操作拆成了 3 个同一普通位运算的修改操作。

现在的压力来到查询。不妨尝试类似地去统一贡献形式：对查询拆位，那我们实际上是一部分位贡献区间按位与，一部分位贡献区间按位或，剩下的贡献区间按位异或。所以我们只要把三种区间位运算的结果查出来，只保留对应位的结果，再合并起来就好了。

时间复杂度 \mathcal O((n+q)\log n)，可以通过。

int n,m,q;
ull a[N];
bool b[N];
string opt[N];
#define mid (l+r>>1)
struct Info{
    ull vand,vor,vxor;
    int len;
    friend Info operator+(const Info &p,const Info &q){
        return {p.vand&q.vand,p.vor|q.vor,p.vxor^q.vxor,p.len+q.len};
    }
};
struct Tag{
    ull f0,f1;
    friend Info operator*(const Info &p,const Tag q){
        ull both=q.f0&q.f1;
        ull nand=both|(q.f1&p.vand)|(q.f0&~p.vor);
        ull nor=both|(q.f1&p.vor)|(q.f0&~p.vand);
        ull nxor=((p.len&1)?q.f0:0ull)^(p.vxor&(q.f1^q.f0));
        return {nand,nor,nxor,p.len};
    }
    friend Tag operator*(const Tag &p,const Tag q){
        ull h0=((~p.f0)&q.f0)|(p.f0&q.f1);
        ull h1=((~p.f1)&q.f0)|(p.f1&q.f1);
        return {h0,h1};
    }
};
struct sgt{
    Info k[N<<2];
    Tag lzy[N<<2];
    il void build(int p,int l,int r){
        lzy[p]={0,(ull)-1};
        if(l==r){
            k[p]={a[l],a[l],a[l],1};
            return;
        }
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        k[p]=k[p<<1]+k[p<<1|1];
    }
    il void pushdown(int p){
        lzy[p<<1]=lzy[p<<1]*lzy[p],lzy[p<<1|1]=lzy[p<<1|1]*lzy[p];
        k[p<<1]=k[p<<1]*lzy[p],k[p<<1|1]=k[p<<1|1]*lzy[p];
        lzy[p]={0,(ull)-1};
    }
    il void modify(int p,int l,int r,int ml,int mr,int op,ull x){
        if(ml<=l&&r<=mr){
            Tag d;
            if(op==0) d={0,x};
            else if(op==1) d={x,(ull)-1};
            else d={x,x^((ull)-1)};
            lzy[p]=lzy[p]*d,k[p]=k[p]*d;
            return;
        }
        pushdown(p);
        if(ml<=mid) modify(p<<1,l,mid,ml,mr,op,x);
        if(mid<mr) modify(p<<1|1,mid+1,r,ml,mr,op,x);
        k[p]=k[p<<1]+k[p<<1|1];
    }
    il Info query(int p,int l,int r,int ml,int mr){
        if(ml<=l&&r<=mr) return k[p];
        pushdown(p);
        if(ml<=mid&&mid<mr) return query(p<<1,l,mid,ml,mr)+query(p<<1|1,mid+1,r,ml,mr);
        else if(ml<=mid) return query(p<<1,l,mid,ml,mr);
        else return query(p<<1|1,mid+1,r,ml,mr);
    }
} T;
#undef mid
struct query{
    int op,l,r,t;
    ull x;
} Q[N];
ull ans[N];
int main(){
#ifdef Ltp
    freopen("hack.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    fr1(i,1,n) cin>>a[i];
    fr1(i,1,m) cin>>opt[i];
    T.build(1,1,n);
    fr1(i,1,q){
        int op,l,r,t;
        ull x;
        cin>>op>>l>>r>>t;
        if(op==1){
            cin>>x;
            ull opa=(ull)-1,opo=0,opx=0;
            fr1(j,0,62){
                if(opt[t][j]=='A'){
                    if(!((x>>j)&1)) opa^=(1ull<<j);
                }
                else if(opt[t][j]=='O') opo|=((x>>j)&1)<<j;
                else opx^=((x>>j)&1)<<j;
            }
            T.modify(1,1,n,l,r,0,opa);
            T.modify(1,1,n,l,r,1,opo);
            T.modify(1,1,n,l,r,2,opx);
        }
        else{
            Info ans=T.query(1,1,n,l,r);
            ull res=0;
            fr1(j,0,62){
                if(opt[t][j]=='A') res|=((ans.vand>>j)&1)<<j;
                else if(opt[t][j]=='O') res|=((ans.vor>>j)&1)<<j;
                else res|=((ans.vxor>>j)&1)<<j;
            }
            cout<<res<<'\n';
        }
    }
    ET;
}
//ALL FOR Zhang Junhao.