526互联

# P5522 [yLOI2019] 棠梨煎雪 题解

发布时间 2023-11-15 16:56:21作者: DengStar

P5522 [yLOI2019] 棠梨煎雪 题解

题目链接

分析1

抛开时间复杂度不谈，先来看看对于每次询问，如何计算合法的字符串个数。

对于每次询问的 \([l,r]\)，我们可以对字符串的每一位按以下种情况讨论（设讨论的这一位为第 \(i\) 位）：

  1. \(str[l..r][i]\) 既有 0 又有 1。那么无解。
  2. \(str[l..r][i]\) 中有一个是 0 或 1，剩下的为 ?。那么这一位只有一种情况。
  3. \(str[l..r][i]\) 全部为 ?。那么这一位有两种情况，填 0 或填 1 都可以。

显然，只有第三种情况才会对答案有贡献。设这种情况的位数为 \(cnt\)，那么根据乘法原理，可能的字符串数就是 \(2^{cnt}\)。

举几个例子：

  1. 求 \(\texttt{11?1}, \texttt{1??1}\) 限定下的可能的字符串。
    第 1 位，第 4 位都为 1，这两位对答案无贡献；第 2 位既有 1 又有 0，该位只能填 0，对答案无贡献；第 3 位全为 ?，既可以填 0 又可以填 1。综上，可能的字符串 \(S\) 有两个：\(S_1 = \texttt{1101},S_2 = \texttt{1111}\)。

  2. 求 \(\texttt{01?1}, \texttt{11?1}\) 限定下的可能的字符串。

    两个字符串的第 1 位既有 0 又有 1，因此不存在可能的字符串。

我们的问题就变成了：

  1. 求出是否存在第一种情况的位，用来判断是否无解。
  2. 如果有解，求出第三种情况的位数，用来计算答案。

分析2

暴力的时间复杂度是 \(O(qmn)\)，显然不行。

由于我们要求的东西是可以按区间合并的，于是很自然地想到用线段树维护：

struct Segment_tree
{
    int left, right;
    bool ex0[MAXL], ex1[MAXL], full2[MAXL];
    // ex0[i] 和 ex1[i] 分别表示第 i 位是否存在 '0' 或 '1'
    // full2[i] 表示第 i 位是否全为 '?'
}t[MAXN << 2];

但是，如果这么写，每次 update，change 和 query 都是 \(O(n)\) 的，总的时间复杂度为 \(O(qn \log m)\)。虽然 \(n\) 很小，但是仍然过不了。考虑优化。

分析3

\(n\) 很小，考虑状压。

把分析 2 中的 ex0[],ex1[],full2[] 都从 bool 数组改成一个 int。由于 \(n \le 30\)，一个 int 足以存下。其他的操作基本上没有变化，但每次 update，change 和 query 的时间复杂度降到了 \(O(1)\)，总的时间复杂度为 \(O(q \log m)\)，轻松跑过。

（另外，change 的时间复杂度是 \(O(\log m) + O(n)\) 的。）

具体详见完整代码：

// P5522 [yLOI2019] 棠梨煎雪
#include<bits/stdc++.h>
#define lson (id << 1)
#define rson (id << 1 | 1)

using namespace std;

const int MAXM = 1e6 + 10, MAXL = 33;
int n, m, q, ans;
int pw[31] = {1};
char str[MAXM][MAXL], s[MAXL];
bool flag;
struct Segment_tree
{
	int left, right;
	int ex0, ex1, full2; 
}t[MAXM * 3];

struct Node
{
	int sta0, sta1, sta2;
	Node(int sta0 = 0, int sta1 = 0, int sta2 = 0): sta0(sta0), sta1(sta1), sta2(sta2) {} 
};

Node merge(Node A, Node B)
{
	return Node(A.sta0 | B.sta0, A.sta1 | B.sta1, A.sta2 & B.sta2);
}

void update(int id)
{
	t[id].ex0 = t[lson].ex0 | t[rson].ex0;
	t[id].ex1 = t[lson].ex1 | t[rson].ex1;
	t[id].full2 = t[lson].full2 & t[rson].full2;
	// 注意位运算的符号：“存在”是按位或，“全为”是按位与。
}

void buildtree(int id, int l, int r)
{
	t[id].left = l, t[id].right = r;
	if(l == r)
	{
		for(int i = 1; i <= n; i++)
		{
			switch(str[l][i])
			{
				case '0': t[id].ex0 |= (1 << (i-1)); break;
				case '1': t[id].ex1 |= (1 << (i-1)); break;
				case '?': t[id].full2 |= (1 << (i-1)); break;
			}
		}
		return;
	}
	int mid = (l + r) >> 1;
	buildtree(lson, l, mid), buildtree(rson, mid + 1, r);
	update(id);
}

Node query(int id, int l, int r)
{
	if(l == t[id].left && r == t[id].right) return Node(t[id].ex0, t[id].ex1, t[id].full2);
	if(r <= t[lson].right) return query(lson, l, r);
	else if(l >= t[rson].left) return query(rson, l, r);
	else return merge(query(lson, l, t[lson].right), query(rson, t[rson].left, r));
}

void change(int id, int pos)
{
	if(pos == t[id].left && pos == t[id].right)
	{
		t[id].ex0 = t[id].ex1 = t[id].full2 = 0;
		for(int i = 1; i <= n; i++)
		{
			switch(s[i])
			{
				case '0': t[id].ex0 |= (1 << (i-1)); break;
				case '1': t[id].ex1 |= (1 << (i-1)); break;
				case '?': t[id].full2 |= (1 << (i-1)); break;
			}
		}
		return;
	}
	if(pos <= t[lson].right) change(lson ,pos);
	else if(pos >= t[rson].left) change(rson, pos);
	update(id);
}

int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= m; i++) scanf("%s", str[i] + 1);
	for(int i = 1; i <= n; i++) pw[i] = pw[i-1] << 1;
	buildtree(1, 1, m);
	int l, r, pos;
	while(q--)
	{
		int opt;
		scanf("%d", &opt);
		if(opt == 0)
		{
			scanf("%d%d", &l, &r);
			Node S = query(1, l, r);
			if(S.sta0 & S.sta1) continue; // 如果在某一位上既有 0 又有 1，不合法
			int cnt = __builtin_popcount(S.sta2);
			// __builtin_popcount(x)：返回 x 在二进制下 1 的个数
			ans ^= pw[cnt];
		}
		else
		{
			scanf("%d%s", &pos, s + 1);
			change(1, pos);
		}
	}
	printf("%d\n", ans);
	return 0;
}

PS：这几天做题状态感觉很差，看到什么题都写不出来，于是强迫自己到洛谷官方题单里找了一道线段树题来做，没想到瞎自己琢磨了一个多小时后居然一发入魂，直接 AC！善哉善哉