题解：AT_arc203_d [ARC203D] Insert XOR

题目描述

另有一串 $\texttt{01}$ 序列 $B$（下标从 $1$ 开始编号）。可以对其进行任意次操作，每次选取一个 $i\isin [1,|B|)$，在 $B_i$ 和 $B_{i+1}$ 之间插入 $B_i \oplus B_{i+1}$。
在 $B$ 能经过上述操作变换得到 $A$ 的前提下，求出 $|B|$ 的最小值。

解题思路

引理 1

$A$ 中每个长度为 $x$ 的 $\texttt{0}$ 连通块，都只能由 $B$ 中对应的长度为 $y$ 的 $\texttt{0}$ 连通块变换得到。其中 $x\ge y\ge 2$。

证明显然，掺入任何一个 $\texttt{1}$ 都不行。

引理 2

形如 $\texttt{1...10}$ 的串，可以只从 $\texttt{10}$ 开始变换得到。其中“$\texttt{...}$”是任意长度的 $\texttt{01}$ 串（当然可以是空串），且不包括任何长度 $\ge 2$ 的 $\texttt{0}$ 连通块。

构造方式为，先将 $\texttt{10}$ 变换成 $\texttt{11}\underbrace{\texttt{.....}}_{\texttt{many '1's}}\texttt{110}$，使得 $\texttt{1}$ 的数量符合要求；再在某些 $\texttt{11}$ 之间插入 $\texttt{0}$ 即可。

注：对称情况同理。

引理 3

形如 $\underbrace{\textcolor{red}{\texttt{00..0}}\textcolor{blue}{\texttt{...}}\textcolor{red}{\texttt{00..0}}\textcolor{blue}{\texttt{...}}}_{\texttt{(repetitive)}}\textcolor{red}{\texttt{00..0}}$ 的串，其最短能从 $\underbrace{\texttt{001001}}_{\texttt{(repetitive)}}\texttt{00}$ 变换得到。
其中标红的 $\textcolor{red}{\texttt{00..0}}$ 是长度 $\ge 2$ 的 $\texttt{0}$ 连通块，每个连通块相对应地由长度 $=2$ 的 $\texttt{00}$ 生成（引理 1）。
标蓝的 $\textcolor{blue}{\texttt{...}}$ 是任意长度的 $\texttt{01}$ 串，且不包括任何长度 $\ge 2$ 的 $\texttt{0}$ 连通块（并且头尾两端的字符必须是 $\texttt{1}$）。可由对应的 $\texttt{1}$ 跟其旁边的 $\texttt{00}$ 生成（引理 2）。

引理 4

形如 $\textcolor{green}{\texttt{0}}\textcolor{blue}{\texttt{...}}\textcolor{red}{\texttt{00..0}}$ 的串，其最短能从 $\texttt{0100}$ 变换得到；
形如 $\textcolor{green}{\texttt{1}}\textcolor{blue}{\texttt{...}}\textcolor{red}{\texttt{00..0}}$ 的串，其最短能从 $\texttt{100}$ 变换得到。
其中 $\textcolor{red}{\texttt{00..0}}$ 和 $\textcolor{blue}{\texttt{...}}$ 意义同 引理 3。

注：对称情况同理。

• 若 $A$ 串包含长度 $\ge 2$ 的 $\texttt{0}$ 连通块，则 $A$ 一定形如 $\textcolor{green}{\texttt{....}}\underbrace{\textcolor{red}{\texttt{00..0}}\textcolor{blue}{\texttt{...}}\textcolor{red}{\texttt{00..0}}\textcolor{blue}{\texttt{...}}}_{\texttt{(repetitive)}}\textcolor{red}{\texttt{00..0}}\textcolor{green}{\texttt{....}}$。
  将答案 $\text{ans}$ 初值设为 $($ $\textcolor{red}{\texttt{00..0}}$ 的个数 $)\times 3-1$，也就是去掉头尾两端的“$\textcolor{green}{\texttt{....}}$”后对应 $\underbrace{\texttt{001001}}_{\texttt{(repetitive)}}\texttt{00}$ 的长度（引理 3）。
  接着讨论头部的“$\textcolor{green}{\texttt{....}}$”对答案的贡献。
  • 若 $\textcolor{green}{\texttt{....}}$ 为空串，则对 $\text{ans}$ 没有贡献；
  • 若 $\textcolor{green}{\texttt{....}}$ 不为空串，则显然要求其末尾字符为 $\texttt{1}$。
    • 若其开头字符为 $\texttt{0}$，则对 $\text{ans}$ 造成 $2$ 的贡献（引理 4）；
    • 若其开头字符为 $\texttt{1}$，则对 $\text{ans}$ 造成 $1$ 的贡献（引理 4）。
  尾部的“$\textcolor{green}{\texttt{....}}$”对答案的贡献同理。
• 若 $A$ 串不包含长度 $\ge 2$ 的 $\texttt{0}$ 连通块，则有：
  • 若 $A$ 串为全 $1$ 串，则 $\text{ans}=n$；
  • 反之若 $A$ 串的开头跟末尾字符均为 $\texttt{0}$，则 $\text{ans}=3$（由 $\texttt{010}$ 生成）；
  • 反之若 $A$ 串的开头跟末尾字符均为 $\texttt{1}$，则 $\text{ans}=2$（由 $\texttt{11}$ 生成）；
  • 反之则 $\text{ans}=2$（由 $\texttt{01}$ 或 $\texttt{10}$ 生成）。
  生成构造方式不难想出。

• 长度 $\ge 2$ 的 $\texttt{0}$ 连通块的个数；
• 长度 $\ge 2$ 的 $\texttt{0}$ 连通块的 第一次 和 最后一次 出现的位置；
• $\texttt{1}$ 的总个数（方便处理 全 $1$ 串 的情况）；
• 开头 和 末尾 的字符。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 10, INF = 0x3f3f3f3f;

int n, q, a[MAXN];

#define left (u << 1)
#define right ((u << 1) | 1)

struct node{
	int res, posl = INF, posr = -INF, cnt1 = 0;
	bool pre, lst;
}t[MAXN << 2];

inline void push_up(node &u, node &lch, node &rch, int l, int r)
{
	int mid = (l + r) >> 1;
	u.cnt1 = lch.cnt1 + rch.cnt1;
	u.pre = lch.pre, u.lst = rch.lst;
	u.posl = min(lch.posl, rch.posl), u.posr = max(lch.posr, rch.posr);
	(!lch.lst && !rch.pre) && (u.posl = min(u.posl, mid), u.posr = max(u.posr, mid + 1));
	if (lch.posr == mid && rch.posl == mid + 1)
		u.res = lch.res + rch.res - 1;
	else if (lch.posr != mid && rch.posl == mid + 1)
		u.res = lch.res + rch.res;
	else if (lch.posr == mid && rch.posl != mid + 1)
		u.res = lch.res + rch.res;
	else if (lch.posr != mid && rch.posl != mid + 1)
		u.res = lch.res + rch.res + (!lch.lst && !rch.pre);
}

inline void build(int u = 1, int l = 1, int r = n)
{
	if (l == r) 
		return
		t[u].pre = t[u].lst = t[u].cnt1 = a[l],
		t[u].posl = INF, t[u].posr = -INF,
		t[u].res = 0, void();
	int mid = (l + r) >> 1;
	build(left, l, mid), build(right, mid + 1, r);
	push_up(t[u], t[left], t[right], l, r);
}

inline void change(int pos, int u = 1, int l = 1, int r = n)
{
	if (l == r)
		return t[u].lst = t[u].cnt1 = (t[u].pre ^= 1), void();
	int mid = (l + r) >> 1;
	if (pos <= mid) change(pos, left, l, mid);
	else change(pos, right, mid + 1, r);
	push_up(t[u], t[left], t[right], l, r);
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", a + i);
	build();
	
	scanf("%d", &q); int x;
	while (q--)
	{
		scanf("%d", &x), change(x);
		if (t[1].cnt1 == n) printf("%d\n", n);
		else if (t[1].cnt1 == 0) printf("%d\n", 2);
		else if (t[1].res)
		{
			int ans = t[1].res * 3 - 1;
			if (t[1].posl != 1) ans += 1 + (!t[1].pre);
			if (t[1].posr != n) ans += 1 + (!t[1].lst);
			printf("%d\n", ans);
		}
		else printf("%d\n", 2 + (!t[1].pre && !t[1].lst));
	}

	return 0;
}