CodeforcesDS1
CF387E George and Cards（2200）
Problem
给出一个 \(1\) 到 \(n\) 的排列（输入中的数组 \(p\) ），并给出一个长为 \(k\) 的数组 \(b\) ，要求从 \(p\) 中删去 \(n - k\) 个元素后得到数组 \(b\) 。
删除操作的定义：选取一个区间 \([l, r]\) ，删去其中最小的元素，并获得 \(r - l + 1\) 的分数。
请你输出最终得分的最大值，保证有解。
\(1 \leq k \leq n \leq 10^{6}\)。
Solution
显然从小到大删，因为如果先把大的数删了，则删小数时能选择的最大区间不变，贡献一定不优。用 set 动态维护比当前数小的数的位置，方便查找以当前数为最小值能选取的最大区间。再用数据结构维护哪些位置的数被删，快速查询以当前数为最小值能选取的最大区间中有多少个数。
\(O(n\log{n})\)。
CF377D Developing Game（2400）
Problem
有 $ n $ 个工人，第 $ i $ 个工人的能力是 $ v_i $，他只与能力在 $ l_i $ 到 $ r_i $ 之间的人在一起工作，问最多能选出多少人一起工作并输出方案。
\(1 \le n \le 10^5\)，\(1 \le l_i \le v_i \le r_i \le 3 \times 10^5\)。
Solution
假设选的工人的集合为 \(S\)，则需满足 \(\max\limits_{i \in S}l_i \le \min\limits_{i \in S}v_i \le \max\limits_{i \in S}v_i \le \min\limits_{i \in S}r_i\)。
然后是一个非常关键的转化：上式成立，等价于能够找到一个二元组 \((L, R)\) 使得 \(\max\limits_{i \in S}l_i \le L \le \min\limits_{i \in S}v_i, \max\limits_{i \in S}v_i \le R \le \min\limits_{i \in S}r_i\)。
把二元组 \((L, R)\) 视作二维平面上的一个点，把一个工人 \((l_i, v_i, r_i)\) 视作矩形 \((l_i, v_i) \sim (v_i, r_i)\)，原问题等价于找到一个点使得被最多的矩形覆盖，相当于 把 \(\max, \min\) 这类多重限制转化成对多个矩形求交。
然后就可以扫描线了。
CF809D Hitchhiking in the Baltic States（2900）
洛谷：CF809D Hitchhiking in the Baltic States
Codeforces：CF809D Hitchhiking in the Baltic States
Problem
给出 \(n\) 个区间 \([l_i,r_i]\) 和 \(n\) 个未知数 \(a_1,a_2,\dots,a_n\)，现在你要确定这 \(n\) 个数，使得 \(a_i\in[l_i,r_i]\)，并且这个序列的最长严格上升子序列尽可能大，求这个最大值。
\(1 \leq n\leq 3\times 10^5\)，\(1 \leq l_i,r_i\leq 10^9\)。
Solution
设 \(f_{x}\) 表示以数字 \(x\) 结尾的最长上升子序列长度，但转移非常困难。
交换状态，设 \(f_x\) 表示最长上升子序列长度为 \(x\) 时结尾的最小数字，则对于当前区间 \([l, r]\) 有以下转移：
- 设 \(i\) 表示使得 \(f_i < l\) 的最大值，则 \(f_{i + 1} \xleftarrow{\min} l\)。由于 \(f_{i + 1} \ge l\)，所以 该更新一定可以被执行，即可以直接令 \(f_{i + 1} = l\)。
- 设 \(j\) 表示使得 \(f_j < r\) 的最大值，则 \(\forall k \in [i + 1, j]\)，\(f_{k + 1} \xleftarrow{\min} f_{k} + 1\)。由于 \(f_{k + 1} > f_{k}\)（严格上升），所以 该更新一定可以被执行，即可以直接令 \(f_{k + 1} = f_k + 1\)。
去掉 \(\min\) 的操作后，DP 值的更新应该？就比较可做了。然而后面是我基本没见过的平衡树优化 DP。
考虑用平衡树维护 \(f\)，\(f_{k + 1} = f_k + 1\) 相当于将 \([i + 1, j]\) 内的 \(f\) 整体右移一个单位再整体加一，\(f_{i + 1} = l\) 相当于在被右移的区间前插入一个值为 \(l\) 的元素。注意如果原来存在 \(f_{j + 1}\)，还要将该元素删去。最终答案为平衡树的大小减一（\(f_0\)）。
tips：
- 理论上 DP 值是互不相同的。但由于整体加一的存在，平衡树中可能出现相同的 DP 值，注意实现时不要将它们都删掉。
CF145E Lucky Queries（2400）
Codeforces：CF145E Lucky Queries
Problem
给你 \(n\) 个数，每个数是 \(4\) 或者 \(7\) ，给你 \(m\) 个任务完成：
switch l r 把 \([l,r]\) 位置的 \(4\) 换成 \(7\) , \(7\) 换成 \(4\)。
count 计算 \(n\) 个数的最长不下降子序列的长度。
\(1 \le n \le 10^6\)，\(1 \le m \le 3 \times 10^5\)。
Solution
评高了。线段树维护：
- 区间 \(4\) 的数量；区间 \(7\) 的数量。
- 区间最长不下降子序列长度；区间最长不上升子序列长度。
pushup 是简单的，pushdown 时进行两次交换即可。
CF811E Vladik and Entertaining Flags（2600）
洛谷：CF811E Vladik and Entertaining Flags
Codeforces：CF811E Vladik and Entertaining Flags
Problem
在一个 \(n\times m\) 的网格上每个格子都有颜色，\(q\) 次询问，每次询问只保留 \(l\) 至 \(r\) 列时有多少个四连通的颜色块。两个格子同色但不连通算在不同的颜色块内。
\(1 \le n \le 10\)，\(1 \le m, q \le 10^5\)。
Solution
强行用线段树维护并查集。需要维护的信息是：
- 区间内连通块数量。
- 左右两列每行所属的连通块编号。
在左右节点合并信息时，只可能是中间两列对应的连通块信息发生改变，对这两列的元素做一遍并查集更新以上信息。
tips：
- 合并时，需要将左右两列和中间两列重新初始化（令父亲等于自己），因为之前的询问可能将某些元素合并到当前查询区间之外。
CF1661E Narrow Components（2500）
CF607D Power Tree（2600）
Problem
一棵树初始只有一个编号为 \(1\) 的权值为 \(w_1\) 的根。\(q(q\le2\times10^5)\) 次操作，每次可以给出 \(v,w(w<10^9)\)，新建一个结点作为 \(v\) 的子结点，权值为 \(w\)；或者给出 \(u\)，求出 \(f(u)\)。定义 \(f(u)=|S|\cdot\sum_{d\in S}d\)，其中 \(S\) 为 \(w_u\) 与其所有子结点 \(v\) 的 \(f(v)\) 构成的可重集合。
Solution
记 \(d_{u}\) 表示 \(u\) 的儿子数量加一。
拆贡献：若查询 \(f(u)\)，则考虑 \(u\) 的子树内的每个点 \(x\) 对 \(u\) 的贡献为：\(w_{x} \times \prod\limits_{z \in path(x, u)}d_{z}\)。
后面的乘积显然可以前缀积计算。记 \(g_{u} = \prod\limits_{z \in path(u, 1)}d_{z}\)，\(h_{u} = \prod\limits_{z \in path(u, 1)}d_z \times w_z\)。
加入一个点 \(u\)：记 \(fa\) 表示 \(u\) 的父节点，则会使 \(d_{fa}\) 加一，\(d_u = 1\)，并使 \(fa\) 子树内的所有节点的 \(g, h\) 值乘上 \(\frac{d_{fa} + 1}{d_{fa}}\)。注意还要新增 \(u\) 节点本身的贡献。
查询 \(f(u)\)：记 \(fa\) 表示 \(u\) 的父节点，则答案为 \(u\) 子树内的 \(h\) 和除以 \(g_{fa}\)。
以上均可用线段树维护。
CF1436E Complicated Computations（2400）
Problem
求一个数列的所有子区间的 mex 值的 mex。
某个数组的 mex 是这个数组中没有包含的最小 正整数。
\(1 \le n \le 10^5\)，\(1 \le a_i \le n\)。
Solution
吗的。跟我组的模拟赛撞题了。
CF1175F The Number of Subpermutations（2500）
Problem
给定数组\(a_1,a_2 \cdots a_n\)，若子序列\(a_l,a_{l+1}\cdots a_{r}\)满足\(1,2\cdots r-l+1\)所有整数各出现一次，则称其为这个数组的一个子排列。求这个数组子排列个数。
\(1 \le n \le 3 \times 10^5\)，\(1 \le a_i \le n\)。
Solution
CF1146E Hot is Cold（2400）
Problem
有一个数列，每次操作会给定 \(x\) 和不等号（大于号或小于号），可以将 \(>x\) 或 \(<x\) 的所有数乘 \(-1\)。求最后的数列。
\(1 \le n, q \le 10^5\)，\(-10^5 \le a_i \le 10^5\)。
Solution
轻度分类讨论。
显然对值域维护一棵线段树。我们需要维护初始值为 \([-N, N]\) 在操作之后的符号。然后直接开始分讨。
-
若 \(s = \text{>}\)：
- 若 \(x \ge 0\)：
- 对于 \([-N, - x - 1] \cup [x + 1, N]\)：区间赋为负号。
- 对于 \([-x, x]\)：无修改。
- 若 \(x < 0\)：
- 对于 \([-N, x] \cup [-x, N]\)：区间赋为负号。
- 对于 \([x + 1, -x - 1]\)：区间取反。
- 若 \(x \ge 0\)：
-
若 \(s = \text{<}\)：
-
若 \(x \le 0\)：
- 对于 \([-N, x - 1] \cup [-x + 1, N]\)：区间赋为正号。
- 对于 \([-x, x]\)：无修改。
-
若 \(x > 0\)：
- 对于 \([-N, -x] \cup [x, N]\)：区间赋为正号。
- 对于 \([-x + 1, x - 1]\)：区间取反。
-
CF1221F Choose a Square（2400）
Problem
有 \(n\) 个点，每个点其坐标 \(x_i,y_i\) 与权值 \(c_i\)，其中 \(1\le n\le 5\times 10^5,0\le x_i,y_i\le 10^9,-10^6\le c_i\le 10^6\)。
让你选一个正方形，该正方形的左下角及右上角必须在 \(y=x\) 这条直线上。所获得的权值为在正方形内的点的权值和减去正方形的边长。
输出所获的最大权值及其选择正方形的左下角 \(x_1,y_1\) 及右上角 \(x_2,y_2\)，要求 \(0\le x_1=y_1\le x_2=y_2\le 2\times 10^9\)。
Solution
记所选正方形的左下角为 \((l, l)\)，右上角为 \((r, r)\)。
包含点 \((x, y)\) 的条件为：\(l \le x, y \le r\)。
把 \((x, y)\)，\((l, r)\) 看作是线段（如果 \(x > y\) 则进行交换），则原问题转化为在数轴上选择一段区间 \([l, r]\)，获得的权值为 \([l, r]\) 完整覆盖的线段的权值和减去 \(r - l\)。
然后用线段树对每个 \(l\) 维护一下 \([l, i]\) 的价值减代价即可。
CF1418G Three Occurrences（2500）
Problem
现在给你一个由 \(n\) 个整数组成的数组 \(a\) ，我们表示子数组 \(a[l\dots r]\) 为数组 \([a_l,a_{l+1}\dots ,a_r](1\le l \le r \le n)\) 。
如果子数组中出现的每个整数恰好出现了三次，我们则称这个子数组为好子数组。例如，数组 \([1,2,2,2,1,1,2,2,2]\) 有三个好子数组：
- \(a[1..6]=[1,2,2,2,1,1] ;\)
- \(a[2..4]=[2,2,2] ;\)
- \(a[7..9] = [2, 2, 2]\).
求这个数组 \(a\) 中有多少个好子数组。
\(1 \le n \le 5 \times 10^5\)，\(1 \le a_i \le n\)。
Solution
CF258E Little Elephant and Tree（2400）
Problem
对一棵根节点编号为 \(1\)，节点数为 \(n\) 的有根树进行 \(m\) 次操作。
这棵树每个节点都有一个集合。
第 \(i\) 次操作给出 \(a_i\) 和 \(b_i\)，把 \(i\) 这个数字放入 \(a_i\) 和 \(b_i\) 这两个点为根的子树里的所有集合中。（包括 \(a_i\) 和 \(b_i\)）
在操作完后，输出 \(c_i\)，\(c_i\) 表示有多少个结点（不包括 \(i\)）的集合至少与 \(i\) 结点的集合有一个公共数字。
\(1 \le n, m \le 10^5\)。
Solution
CF1771F Hossam and Range Minimum Query（2500）
Problem
- 给你一个长度为 \(n\) 的非负整数序列 \(a\)。
- 有 \(q\) 次询问，每次询问 \([l,r]\) 中满足出现次数为奇数的数当中，最小的那个是哪个数，不存在则输出 \(0\)。
- 强制在线，你输入的 \(l',r'\) 需要异或上上一次的答案 \(\operatorname{lastans}\) 才是真正的 \(l,r\)，若此时为第一次询问或上一次询问不存在出现次数为奇数的数，则 \(\operatorname{lastans}=0\)。
- \(1\leq n,q\leq 2\times10^5,0\leq a_i\leq 10^9,1\leq l',r'\leq2\times 10^9\)。
Solution
给 \(a\) 数组的数赋上一个随机权值，则区间出现次数为奇数等价于随机权值异或和不为 \(0\)。
用以值域为下标的主席树维护一段连续值域的前缀异或和的异或和 \(x\)，则该值域内存在奇数次数的数对应 \(x \neq 0\)（由于随机权值，所以存在奇数次数的数但异或和为 \(0\) 的概率极小）。
在线段树上二分即可。如果左值域异或和为 \(0\) 则查询右值域。
CF935F Fafa and Array（2600）
CF1085F Rock-Paper-Scissors Champion（2500）
CF1858E2 Rollbacks (Hard Version)（2600）
CF1870G MEXanization（3300）
CF266E More Queries to Array...（2500）
CF1148H Holy Diver（3500）
CF1295E Permutation Separation（2200）
CF916E Jamie and Tree（2400）
CF794F Leha and security system（2800）
CF295E Yaroslav and Points（2500）
CF785E Anton and Permutation
CF407E k-d-sequence
CF1746F Kazaee
CF573E Bear and Bowling（3200）
CF533A Berland Miners
CF533D Landmarks
CF893F Subtree Minimum Query
强化版 BZOJ#4771：维护子树内不同颜色的出现次数
CF1083C Max Mex
CF1030F Putting Boxes Together
CF1797E Li Hua and Array
*CF1804G Flow Control
CF1805E There Should Be a Lot of Maximums
CF1810F M-tree
CF1814E Chain Chips
*CF1827F Copium Permutation
CF1830E Bully Sort
CF1842E Tenzing and Triangle
CF19D Points（2800）
Problem
在一个笛卡尔坐标系中，定义三种操作:
-
add x y:在坐标系上标记一个点 \((x,y)\)，保证 \((x,y)\) 在添加前不在坐标系上。 -
remove x y:移除点 \((x,y)\)，保证 \((x,y)\) 在移除前已在坐标系上。 -
find x y:找到所有已标记并在 \((x,y)\) 右上方的点中，最左边的点，若点不唯一，选择最下面的一个点; 如果没有符合要求的点，给出-1，否则给出\((x,y)\)。
现有 \(n\) 个操作,对于每个 find 操作，输出结果。\(n \le 2 \times 10^5\)，\(0 \le x,y \le 10^9\)。
Solution
离散化后，对每一个横坐标开一个 set 去维护对应的纵坐标，并用线段树维护每个横坐标最大的纵坐标的值。每次询问在对应的横坐标区间上去线段树二分，找到符合要求的最小横坐标，再在这个横坐标的 set 上进行 lower_bound，找到符合要求的最小纵坐标。远古 CF，评 2800* 真的太过了。
\(O(n\log{n})\)。