【S-C1】是啥意思？？
01. CF1858E2 Rollbacks (Hard Version)
维护一个初始为空的序列 \(a\)，支持以下操作：
- \(\texttt{+ }x\)：在序列末端插入 \(x\)；
- \(\texttt{- }k\)：在序列末端删除 \(k\) 个数（\(k\) 不超过当前序列长度）；
- \(\texttt{?}\)：查询序列中不同的数字个数；
- \(\texttt{!}\)：撤回前一个 \(\texttt +/\texttt -\) 操作。
\(q\) 次操作，强制在线，\(1\le q,x\le 10^6\)，询问操作不超过 \(10^5\)。
解法
垃圾 *2600。
经典地，我们用 set 维护所有数字的出现的所有位置，更新时只需要查询其首位即可。
这样我们可以轻松实现 \(\texttt +\) 操作。
为了实现 \(\texttt -\) 操作，我们引入序列 \(A\)，使得序列 \(A\) 的前 \(l\) 位恰好为序列 \(a\)（\(l\) 为序列 \(a\) 此时的长度）。这样一来，我们更新时直接将 \(l\) 更改为 \(l-k\) 即可。
这样做同样是为了方便进行 \(\texttt !\) 操作。因为我们实际上保留了 \(1\sim l_{\max}\) 的所有信息，足以进行回溯。
对于 \(\texttt !\) 操作，我们使用 stack 存储所有操作，并尝试逆向地进行还原，具体情况与上面的 \(\texttt +/\texttt -\) 操作思路一致。
特别地，对于 \(\texttt +\) 操作，我们需要存储原来的 \(A_{l'}\) 而不是 \(x\)。这是容易理解的。
至于答案的更新，我们在所有元素第一次出现的位置标记为 \(1\)，这个是已经维护过的。
那么 \(\texttt ?\) 操作只需要输出该数组在 \([1,l]\) 上的区间和即可。
至此，我们需要一个可以支持单点修改、查询区间和的数据结构。拉一个树状数组即可。
时间复杂度 \(O(q\log q)\)。
https://codeforces.com/contest/1858/submission/219045104
考虑优化，逐个解决瓶颈：
- 树状数组：可以用前缀和替代。容易发现是可行的；
- 维护各个元素出现的位置：我们发现改变一个元素第一次出现的位置，必然伴随着一个当前已知位置该元素的更新或该元素的彻底删除。据此可以只用一个数组 \(pos\) 代替上述题解中提出的 set 进行维护。
据此，我们得到时间复杂度 \(O(q)\) 的做法。代码从略。
02. CF1804F Approximate Diameter
给定一个 \(n\) 个点 \(m\) 条边的初始无向图，有 \(q\) 次更新，每次更新向图中添加一条边。设 \(d(G_i)\) 代表加入 \(i\) 条边后的图中两点之间的最大距离，你需要输出 \(q+1\) 个整数 \(a_0,a_1,\dots,a_q\)，满足 \(\Bigl\lceil\dfrac{d(G_i)}{2}\Bigr\rceil\le a_i\le 2\cdot d(G_i)\)。
\(n,m,q\le 10^5\)，图连通。
解法
牛逼 *2700。
考虑一个性质，以某个点为端点的最长路径长度 \(s\) 满足
\[\Bigl\lceil\dfrac{d(G_i)}2\Bigr\rceil\le s\le d(G_i) \]证明从略。
但是发现这个比要求的更紧。考虑怎么利用这个 \(2\cdot d(G_i)\)。
显然地，我们考虑二分某个答案什么时候失效，此时我们将该答案除以 \(2\) 即可。这是可行的，因为这个一眼单调。
二分枚举端点再套枚举答案即可，时间复杂度 \(O(n\log^2 n)\)。
https://codeforces.com/contest/1804/submission/219393324
注意我们钦点的 dijkstra 算法别写丑，不然无法通过。
03. CF992E Nastya and King-Shamans
给定序列 \(a\)，维护两种操作：
- 单点将 \(a_i\to x\)；
- 查询 \(\sum_{i=1}^n\Bigl[\Bigl(\sum_{j=1}^{i-1}a_j\Bigr)=a_i\Bigr]\)。
\(1\le n,q\le 2\times10^5\)，\(0\le a\le 10^9\)。
解法
还不错的 *2500。
考虑一个性质：答案最多为 \(\log n\)。
证明从略。我们考虑直接拉线段树维护然后暴力遍历即可找到答案。
时间复杂度 \(O(q\log^2 n)\)。
https://codeforces.com/contest/992/submission/219414380
04. CF825G Tree Queries
一棵树有 \(n\) 个节点，初始均为白色，有两种操作：
- \(\texttt{1 } x\)：把节点 \(x\) 染为黑色；
- \(\texttt{2 } x\)：查询 \(x\) 到树上任意一个黑色节点的简单路径上的编号最小的节点的编号。
保证第一个操作为染色操作，强制在线。\(3\le n\le 10^6\)，\(1\le q\le 10^6\)。
解法
小清新 *2500！
首先，显然地，为了方便维护，我们以第一次染色的节点 \(t\) 为根 dfs 一遍以求出所有节点到 \(t\) 的简单路径上的编号最小的节点的编号，即数组 \(a\)。
然后画个图可以理解：
- 对于染色操作，将目前维护的一个答案 \(ans\gets \min(ans,a_x)\)，可以证明这是正确的；
- 对于询问操作，我们输出 \(\min(ans,a_x)\) 即可。
这是因为，我们的对于不同 \(t\) 的子树间的路径 \(u\to v\)，有 \(u\to t\to v\) 即为其简单路径。而对于子树内的路径，可以用 \(u\to t,v\to t\) 覆盖整个路径。
至此问题得到 \(O(n)\) 解决。
https://codeforces.com/contest/825/submission/219512635
05. CF1503D Flip the Cards
你有 \(n\) 张牌，第 \(i\) 张牌的正面有整数 \(a_i\)，背面有整数 \(b_i\)。所有 \(1\) 到 \(2n\) 的整数都出现过正好一次。
我们认为这 \(n\) 张牌是好的当且仅当 \(a_i\) 升序，\(b_i\) 降序。
可以进行下面的操作：
- 交换 \(a_i,b_i\)。
- 随意重排这 \(n\) 张牌。
求如果要使这 \(n\) 张牌变成好的最少需要翻几次牌，或报告无解。
解法
牛逼 *2600。可惜放了 \(\log\) 过。
我们考虑到，若存在一个 \(i\) 使得 \(a_i,b_i\le n\)，则必然无解。
于是考虑将所有牌变成 \(a_i<b_i\) 的情况，则必然有 \(a_i\le n,b_i>n\)。于是设 \(f(a_i)=b_i\)。
下面研究 \(f(i)\)。发现当且仅当 \(f(1\ldots n)\) 可以被分为两个单调递减子序列使有解。
在 \(\min_{j=1}^i\{a_j\}>\max_{j=i+1}^n\{a_j\}\) 处断点分段处理最小值即可。
时间复杂度 \(O(n)\)，远超 \(\log\) 且更巧妙。
同时注意到没必要管顺序。
https://codeforces.com/contest/1503/submission/219536981
06. CF1646F Playing Around the Table
有 \(n\) 个人坐成一个圈，每个人手上有 \(n\) 张麻将，麻将上是 \(1\) 萬到 \(n\) 萬，每次可以让每个人同时掏出一张麻将给下一个人，构造一组方案使得第 \(i\) 个人能够做成「\(i\) 萬一色」。
要求，操作次数不超过 \(n^2-n\)；\(1\le n\le 100\)。
解法
萌萌 *2900。
我们考虑到，为了方便处理，设计一个过渡态「一气通贯」使所有情况达到统一。
可以证明，初态 \(\to\)「一气通贯」\(\to\)「\(i\) 萬一色」这一变换中，第一步的操作次数不超过 \(n(n-1)/2\)，第二步的操作次数为 \(n(n-1)/2\)。
下面，我们证明第一个。发现离「一气通贯」最远的状态是每个人均有一个「\(j\) 萬一色」，证毕。
https://codeforces.com/contest/1646/submission/219623330
感觉还是比较难想的，所以场上才仅 3 人通过。
07. CF802H Fake News (medium)
构造字符串 \(s,p\)，使字符串 \(s\) 的为 \(p\) 的子串恰有 \(n\ (1\le n\le 10^6)\) 个。
解法
萌萌 *2200！感觉思路比较牛逼。
我首先想到了 CF1368B Codeforces Subsequences，不同的是，这道题是至少 \(n\) 个。
一个朴素的想法是，对于恰好有 \(k\) 个子串的情况 \((s,p)\)，我们可以实现 \(k\to 2 k\)。
具体地，任取一个新字符 \(c\)，令 \(s'=scc\)，\(p'=pc\) 即可（这里直接用字符串拼接表示了）。
但是我们不能实现 \(k\to k+1\)。这是很困难的。否则我们可以直接二进制拆分 \(n\) 解决。
考虑另一个思路，假设对于恰好有 \(k\) 个子串的情况 \((s,p)\)，\(s\) 可以被表示为 \(pu\)（\(u\) 也是一个字符串），任取一个新字符 \(c\)，那么我们可以实现
- \(k\to 2 k+1\)：令 \(s'=pcucc\)，\(p'=pc\) 即可；
- \(k\to 2 k+2\)：令 \(s'=pccucc\)，\(p'=pc\) 即可。
这之后我们均直接可以更新 \(u'\)。
于是我们递归地解决这个问题即可。考虑每次处理 \(x\) 时，先解决 \(\left\lfloor\frac{x-1}2\right\rfloor\) 时的情况，再回溯解决。容易发现这是合理的。
边界是 \(x=1,2\)。这个也是平凡的，只需要使 \(p=\texttt a\) 即可。
这个是很对的，不考虑 string 类的复杂度是 \(O(\log n)\)。由于 \(2^{26}>10^6\)，我们可以仅用小写字母解决本题。
https://codeforces.com/contest/802/submission/219735685
标签：10,le,texttt,即可,操作,C1,杂题,我们 From： https://www.cnblogs.com/plenilunesept/p/17645415.html