高质量题集合-526互联

\(\color{royalblue}{P5522\ [yLOI2019]\ 棠梨煎雪}\)

思路：线段树+状压

复杂度：\(O(nq+q\log_2m)\)

主体思路

第一眼想到开 \(30\) 个线段树维护每一位上的 \(0/1/?\) ，复杂度 \(O(nq\log_2m)\)。考虑把每个字符串的 \(0/1/?\) 状压压进线段树，优化为正解。

具体地，开三个线段树维护 \(l\) 到 \(r\) 之间每一位是否出现 \(0/1/?\)，用 \(or\) 转移，对于答案分几类讨论即可。

\(\text{code:}\)

#define LL long long
#define UN unsigned
#include<bits/stdc++.h>
using namespace std;
//--------------------//
const int N=31,M=1e5+9;

int n,m,q;
char a[M][N],temp[N];
int tem0[M],tem1[M],tem[M];
int ans;
//--------------------//
//Seg-Tree
const int TM=4e5+30;

struct Seg_Tree
{
    struct Seg_Tree_Node
    {
        int l,r;
        int val;
    }t[TM];
    int s[M];

    int ls(int rt){return rt<<1;}
    int rs(int rt){return rt<<1|1;}

    void push_up(int rt){t[rt].val=t[ls(rt)].val|t[rs(rt)].val;}

    void build(int rt,int l,int r)
    {
        t[rt].l=l,t[rt].r=r;
        if(l==r)
        {
            t[rt].val=s[l];
            return;
        }
        int mid=l+r>>1;
        build(ls(rt),l,mid);
        build(rs(rt),mid+1,r);
        push_up(rt);
        return;
    }

    void change(int rt,int pos,int val)
    {
        if(t[rt].l==t[rt].r)
        {
            t[rt].val=val;
            return;
        }
        int mid=t[rt].l+t[rt].r>>1;
        if(pos<=mid)
            change(ls(rt),pos,val);
        else
            change(rs(rt),pos,val);
        push_up(rt);
        return;
    }

    int query(int rt,int l,int r)
    {
        if(t[rt].l>=l&&t[rt].r<=r)
            return t[rt].val;
        int mid=t[rt].l+t[rt].r>>1,res=0;
        if(l<=mid)
            res|=query(ls(rt),l,r);
        if(r>mid)
            res|=query(rs(rt),l,r);
        return res;
    }
}T0,T1,T;
//--------------------//
int count(int x)
{
    int res=0;
    while(x)
    {
        res+=x&1;
        x>>=1;
    }
    return res;
}
int qpow(int base,int k)
{
    int res=1;
    while(k)
    {
        if(k&1)
            res*=base;
        base*=base;
        k>>=1;
    }
    return res;
}
//--------------------//
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=m;i++)
    {
        scanf("%s",a[i]+1);
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]=='0')
                tem0[i]+=1<<(j-1);
            else if(a[i][j]=='1')
                tem1[i]+=1<<(j-1);
            else 
                tem[i]+=1<<(j-1);
        }
    }
    for(int i=1;i<=m;i++)
    {
        T0.s[i]=tem0[i];
        T1.s[i]=tem1[i];
        T.s[i]=tem[i];
        //printf("%d %d %d %d\n",i,tem0[i],tem1[i],tem[i]);
    }
    T0.build(1,1,m);
    T1.build(1,1,m);
    T.build(1,1,m);
    int nowans,now0,now1,now;
    for(int op,x,y,i=1;i<=q;i++)
    {
        scanf("%d%d",&op,&x);
        if(op==0)
        {
            scanf("%d",&y);
            now0=T0.query(1,x,y);
            now1=T1.query(1,x,y);
            now=T.query(1,x,y);
            if(now0&now1)
                nowans=0;
            else
                nowans=qpow(2,count(now^(now&now0)^(now&now1)));
            //printf("%d %d %d %d\n",nowans,now0,now1,now);
            ans^=nowans;
        }
        else
        {
            scanf("%s",temp+1);
            now0=now1=now=0;
            for(int j=1;j<=n;j++)
            {
                if(temp[j]=='0')
                    now0+=1<<(j-1);
                else if(temp[j]=='1')
                    now1+=1<<(j-1);
                else 
                    now+=1<<(j-1);
            }
            T0.change(1,x,now0);
            T1.change(1,x,now1);
            T.change(1,x,now);
        }
    }
    printf("%d",ans);
    return 0;
}