区间操作考虑用线段树维护。
建(n*2)棵线段树，前(n)棵线段树维护每个串的第i位是否是0。
后(n)棵线段树维护每个串的第i位是否是1。
如果是问号的话，直接跳过就好(通过1和0能看出是否是问号)。
然后分三种情况统计答案：
1.有1也有0,不可能，(ans=0)
2.只有1或0，一种情况，(ans)不变。
3.既没有0也没有1，两种情况(ans*=2)
像这样这棵线段树。
但是这样会很慢。
考虑状压。
这样只用开两棵线段树，一个存零，一个存一。
把状态压缩成一个(int),最多30位，转换成十进制(int)能存下。
然后的建树、查询、更改操作其实就是类似一个模板。
建树：
void build(int hao,int l,int r)
{
if(l==r)
{
for(int i=1;i<=n;i++)
{
if(s[l][i]=='?')//问号跳过
{
continue;
}
flag[hao][s[l][i]-'0']|=(1<<(i-1));//状压
}
return;
}
int mid=(l+r)/2;
build(hao<<1,l,mid);
build(hao<<1|1,mid+1,r);
flag[hao][0]=flag[hao<<1][0]|flag[hao<<1|1][0];
flag[hao][1]=flag[hao<<1][1]|flag[hao<<1|1][1];
}
查询：
data query(int hao,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
{
return (data){flag[hao][0],flag[hao][1]};
}
int mid=(l+r)/2;
data kkk=none;
if(L<=mid)
{
kkk=kkk+query(hao<<1,l,mid,L,R);
}
if(R>mid)
{
kkk=kkk+query(hao<<1|1,mid+1,r,L,R);
}
return kkk;
}
我们这里返回一个data的量，以便于后面计算答案。
计算答案的主程序：
scanf("%d%d",&l,&r);
data ans=query(1,1,m,l,r);
anss=1;
for(int i=1;i<=n;i++)//只有1或0的方案数只有一种
{
if(ans.x&1&&ans.y&1)//第i位既有1又有0，不可能。
{
anss=0;
break;
}
if(!(ans.x&1)&&!(ans.y&1))//都是问号
{
anss*=2;
}
ans.x>>=1;
ans.y>>=1;
}
ansss^=anss;
更改：
void change(int hao,int l,int r,int x)
{
if(l==r)
{
flag[hao][0]=flag[hao][1]=0;//单点修改
for(int i=1;i<=n;i++)
{
if(ch[i]=='?')
{
continue;
}
flag[hao][ch[i]-'0']|=(1<<(i-1));
}
return;
}
int mid=(l+r)/2;
if(x<=mid)
{
change(hao<<1,l,mid,x);
}else{
change(hao<<1|1,mid+1,r,x);
}
flag[hao][0]=flag[hao<<1][0]|flag[hao<<1|1][0];
flag[hao][1]=flag[hao<<1][1]|flag[hao<<1|1][1];
}
最后就把这些函数结合在一起就可以了。
#include<bits/stdc++.h>
#define N 400010
using namespace std;
int flag[N<<2][2],n,m,q,op,ansss,l,r,anss;
char s[N][41],ch[41];
struct data
{
int x,y;
}none;
data operator +(data a,data b)
{
return (data){a.x|b.x,a.y|b.y};
}
void build(int hao,int l,int r)
{
if(l==r)
{
for(int i=1;i<=n;i++)
{
if(s[l][i]=='?')//问号跳过
{
continue;
}
flag[hao][s[l][i]-'0']|=(1<<(i-1));//状压
}
return;
}
int mid=(l+r)/2;
build(hao<<1,l,mid);
build(hao<<1|1,mid+1,r);
flag[hao][0]=flag[hao<<1][0]|flag[hao<<1|1][0];
flag[hao][1]=flag[hao<<1][1]|flag[hao<<1|1][1];
}
data query(int hao,int l,int r,int L,int R)
{
if(L<=l&&R>=r)
{
return (data){flag[hao][0],flag[hao][1]};
}
int mid=(l+r)/2;
data kkk=none;
if(L<=mid)
{
kkk=kkk+query(hao<<1,l,mid,L,R);
}
if(R>mid)
{
kkk=kkk+query(hao<<1|1,mid+1,r,L,R);
}
return kkk;
}
void change(int hao,int l,int r,int x)
{
if(l==r)
{
flag[hao][0]=flag[hao][1]=0;//单点修改
for(int i=1;i<=n;i++)
{
if(ch[i]=='?')
{
continue;
}
flag[hao][ch[i]-'0']|=(1<<(i-1));
}
return;
}
int mid=(l+r)/2;
if(x<=mid)
{
change(hao<<1,l,mid,x);
}else{
change(hao<<1|1,mid+1,r,x);
}
flag[hao][0]=flag[hao<<1][0]|flag[hao<<1|1][0];
flag[hao][1]=flag[hao<<1][1]|flag[hao<<1|1][1];
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=m;i++)
{
scanf("%s",s[i]+1);
}
build(1,1,m);
for(int i=1;i<=q;i++)
{
scanf("%d",&op);
if(op==0)
{
scanf("%d%d",&l,&r);
data ans=query(1,1,m,l,r);
anss=1;
for(int i=1;i<=n;i++)//只有1或0的方案数只有一种
{
if(ans.x&1&&ans.y&1)//第i位既有1又有0，不可能。
{
anss=0;
break;
}
if(!(ans.x&1)&&!(ans.y&1))//都是问号
{
anss*=2;
}
ans.x>>=1;
ans.y>>=1;
}
ansss^=anss;
}else{
scanf("%d%s",&l,ch+1);
change(1,1,m,l);
}
}
printf("%d
",ansss);
return 0;
}