题解：AT_arc203_d [ARC203D] Insert XOR

· · 题解

\begin{Bmatrix}\color{red}\LARGE\bold{Solution}\\\normalsize\texttt{No.020 }\bold{AT\_arc203\_d}\end{Bmatrix}\times\footnotesize\texttt{ By Xyz105}

题目描述

给定一串长度为 N 的 \texttt{01} 序列 A。有如下问题：

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

现有 Q 次询问。每次询问会反转 A 的其中一个数，同时要求输出上述问题的答案。3\le N\le 2\times 10^5，Q\le 5\times 10^5。

解题思路

一步一步来。

引理 1

证明显然，掺入任何一个 $\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**。 注：对称情况同理。

综上所述，我们可以分类讨论出，在没有修改操作的情况下题干所述问题的答案。

现在要引入修改操作。可以考虑使用线段树，需要维护的信息为（仅供参考）：

到这里就做完了，总码量不算大。

参考代码

赛时吃了一发罚时。 Submission on AtCoder。

#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;
}