P5522

发表于 分类于
[yLOI2019] 棠梨煎雪

[yLOI2019] 棠梨煎雪

写了一个树状数组，然后被卡常了。

事实上要写一个状压。

然后我们可以存储两个状态 $a_i$ 和 $b_i$。

$a_i$ 的每一位表示这个串的这一位为 0 还是 1，其中为 ? 的位为 0。

然后 $b_i$ 的每一位表示这个串的这一位是否为 ?。

然后就可以瞎搞了。

其实这个 ? 位，在某次查询中，一个位上的 ? 只能全取 0 或全取 1，那么我们想办法实现这个。

于是乎，$a_i\operatorname{xor} b_i$ 就可以让这些位全取 1，$a_i$ 本身就可以让这些位全取 0。

显然前一种值维护区间或，后一种值维护区间与，再多维护一个 $b_i$ 的区间与即可。

线段树维护就好了。

最后看每一位，如果该位不能全 1 并且该位不能全 0 这个区间就是不合法的，否则合法，我们利用 $b_i$ 的区间与看这一位是否都是问号，如果是，使答案乘 2。

时间复杂度 $O(q(n+\log m))$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#define ll long long
using namespace std;

const ll N=30,M=1e5+10;

ll n,m,q,pos,l,r,op,ans;

ll a[M],b[M];

char s[N+10];

struct sgt{
	ll l,r,dat0,dat1,dat2;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define dat0(x) tree[x].dat0
	#define dat1(x) tree[x].dat1
	#define dat2(x) tree[x].dat2
}tree[M*4];

void build(ll p,ll l,ll r) {
	l(p)=l;r(p)=r;
	if(l==r) {
		dat0(p)=a[l];dat1(p)=a[l]^b[l];
		dat2(p)=b[l];
		return;
	}
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);build(p<<1|1,mid+1,r);
	dat0(p)=dat0(p<<1)|dat0(p<<1|1);
	dat1(p)=dat1(p<<1)&dat1(p<<1|1);
	dat2(p)=dat2(p<<1)&dat2(p<<1|1);
	return;
}

sgt ask(ll p,ll l,ll r) {
	if(l(p)>=l&&r(p)<=r) {
		return tree[p];
	}
	ll mid=(l(p)+r(p))>>1;
	if(l>mid) return ask(p<<1|1,l,r);
	if(r<=mid) return ask(p<<1,l,r);
	sgt tmpl=ask(p<<1,l,r),tmpr=ask(p<<1|1,l,r),res;
	res.dat0=tmpl.dat0|tmpr.dat0;
	res.dat1=tmpl.dat1&tmpr.dat1;
	res.dat2=tmpl.dat2&tmpr.dat2;
	return res;
}

void modify(ll p,ll x,ll ka,ll kb) {
	if(l(p)==r(p)) {
		dat0(p)=ka;dat1(p)=ka^kb;
		dat2(p)=kb;
		return;
	}
	ll mid=(l(p)+r(p))>>1;
	if(x<=mid) modify(p<<1,x,ka,kb);
	if(x>mid) modify(p<<1|1,x,ka,kb);
	dat0(p)=dat0(p<<1)|dat0(p<<1|1);
	dat1(p)=dat1(p<<1)&dat1(p<<1|1);
	dat2(p)=dat2(p<<1)&dat2(p<<1|1);
	return;
}

inline ll read() {
	ll ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
	return ret*f;
}

inline void write(ll x) {
	static char buf[22];static ll len=-1;
	if(x>=0) {
		do{buf[++len]=x%10+48;x/=10;}while(x);
	}
	else {
		putchar('-');
		do{buf[++len]=-(x%10)+48;x/=10;}while(x);
	}
	while(len>=0) putchar(buf[len--]);
}

int main() {
	
	n=read();m=read();q=read();
	
	for(ll i=1;i<=m;i++) {
		scanf("%s",s+1);
		for(ll j=1;j<=n;j++) {
			if(s[j]=='0') continue;
			if(s[j]=='1') {
				a[i]|=(1<<(j-1));
			}
			if(s[j]=='?') {
				b[i]|=(1<<(j-1));
			}
		}
	}
	
	build(1,1,m);
	
	while(q--) {
		op=read();
		if(op==0) {
			l=read();r=read();
			sgt tmp=ask(1,l,r);
			ll sum=1;
			for(ll i=1;i<=n;i++) {
				if(((tmp.dat0>>(i-1))&1)&&(!((tmp.dat1>>(i-1))&1))) {
					sum=0;break;
				}
				if((tmp.dat2>>(i-1))&1) sum<<=1;
			}
			ans=ans^sum;
		}
		if(op==1) {
			pos=read();
			scanf("%s",s+1);
			ll tmpa=0,tmpb=0;
			for(ll i=1;i<=n;i++) {
				if(s[i]=='0') continue;
				if(s[i]=='1') {tmpa|=(1<<(i-1));}
				if(s[i]=='?') {tmpb|=(1<<(i-1));}
			}
			modify(1,pos,tmpa,tmpb);
		}
	}
	
	write(ans);
	
	return 0;
}