Codeforces Round #773 (Div.1 )A~D 题解
下大分。
A. Great Sequence
给定正整数 \(x\)。称一个长度为 \(n\) 的序列是好的，当且仅当 \(n\) 是偶数，且可以将 \(a\) 重新排列，使得 \(\forall i,a_{2i-1}\cdot x=a_{2i}\)。
给出一个长度为 \(n\) 的数组 \(x\)，试求至少要添加几个数，使得 \(a\) 序列是好的。
\(n\le 2\times 10^5,2\le x\le 10^6,1\le a_i\le 10^9\)。
分析：
我们要让 \(a\) 中的数尽可能多的两两配对，满足每一对的大数都是小数的 \(x\) 倍。答案是未能成功配对的数的个数。
从小到大枚举 \(a\) 中的数，每次枚举到一个未配对的数 \(v\)，如果还有一个 \(v\cdot x\) 也没配对，就把他们都删去。否则答案加一。
这个贪心是对的，正确性不难证明。
时间复杂度 \(O(n\log n)\)。
B. Repetitions Decoding
称一个长度为 \(n\) 的序列是“重复的”，当且仅当 \(n\) 是偶数，且前一半等于偶一半。
称一个序列是好的，当且仅当它可以被划分成若干个“重复的”序列。
给定一个长度为 \(n\) 序列 \(a\)，你可以进行最多 \(2n^2\) 次操作，每次操作在 \(a\) 的一个位置插入两个相同字符。目标是使得 \(a\) 变成好的序列。
如果无解输出 -1；否则先输出所有的操作，然后输出此时 \(a\) 的任意一种划分方案。注意不需要最小化答案。
分析：
构造是我短板实锤了。
误区是陷入类似分段 dp 的形式去探究把 \(a\) 中的一段变成重复的方案，因为这个东西一不好做，二是通过观察样例 \(2\) 我们注意到我们可以添加一串东西（比如 123321） 然后把一部分划分进左边的重复序列，另外一部分划分进右边的重复序列，这是不好研究和表示的。
需要注意到不能把每次操作添加的字符孤立考虑，因为我们可能会加出 \(11\rightarrow 1221 \rightarrow 122331\) 这样的东西。
那么首先一个事情是任意一个长度为偶数的回文串我们都能添加进去。然后有趣的是此时我们可以翻转 \(a\) 的任意一个子段 \([l,r]\)：我们只要在 \(a_r\) 之后插入回文串 \(s_{l}...s_{r}s_{r}...s_{l}\)，然后把两个挨在一起的 \(s_{l}...s_{r}\) 消去（指划分进一个“重复的”序列）即可。
那么这个问题就可做多了，因为串不会在变化得很厉害了。
套路地，我们思考什么时候无解，显然一个字符出现次数为奇数无解。根据直觉（套路），如果每个字符出现偶数按理来说必定有解的。每个字符出现次数为偶数，容易想到让同种字符之间两两配对。比如 (11)(11)(33)(44)(66) 这样的。换言之我们要让最后的 \(a\) 有序。
所以问题转变成了用区间任意翻转进行排序，这个时候做法就很多了。比较简单的是只利用前缀翻转，然后变成了经典入门题。容易分析出操作上界实质上是 \(O(n(n+1))\) 的。还有一种做法，也是递归的：我们考虑找到 \(a_1\) 的下一次出现位置 \(p\)，然后把 \([2,p]\) 翻转，然后消去 \([a_1,a_2]\)。此时变成了子问题。都很好实现。
C. Anonymity Is Important
有 \(n\) 个布尔变量，然后给出 \(q\) 次操作：
-
0 l r v ：表示第 \(l\sim r\) 个变量的位或和为 \(v(v\in [0,1])\)。
-
1 x ：询问第 \(x\) 个布尔变量是否的值是否能被确定。如果能，输出它的值；否则输出
N/A表示不能确定。
\(n,q\le 2\times 10^5\)。
分析：
良心出题人放了我的 2log 过去。
良心有啥用，这题是 system test 刚结束就交秒过的...
我们意识到，难点在于判断一个变量的值到底是 \(1\) 还是不能确定。
如果 \(x\) 必须是 \(1\)，那么存在一条线段 \([l,r]\) 覆盖 \(x\) 且下标在 \([l,x)\cup(x,r]\) 范围内的变量都是 \(0\)。
我们考虑维护所有确定为 \(0\) 的变量构成的极长连续段。每次询问的时候，\(l=x\lor r=x\) 的情况是容易处理的，我们只关心是否存在 \(l\lt x\lt r\) 的线段满足 \([l,x)\cup(x,r]\) 范围内的变量都是 \(0\)。
那首先 \(l-1,r+1\) 都得是确定为 \(0\)。考虑对每个极长连续段维护一个 \(set\)，对于每个在这个段内的点 \(x\)，\(set\) 中加入所有左端点为 \(x\) 的线段的右端点。那么我们每次就是关注 \(l-1\) 所属于的连续段，它维护的 \(set\) 内是否存在一个在 \(r+1\) 所属的连续段的元素。这可以通过简单的二分完成，不再赘述。
考虑合并极长连续段，可以维护并查集，按照 \(set\) 的大小进行启发式合并，根据按秩合并的理论复杂度应该是 \(O(q\log q)\) 的，每次合并都是 \(set\) 的插入删除，所以复杂度可以视作 \(O(n\log^2 n)\)。