plan R 2

[★★] QOJ7905 Ticket to Ride（#22）

令 $f_{i,j}$ 表示前 $i$ 个段选了 $j$ 段的最大价值，有 $f_{i,j}=\max\limits_{k<i} f_{k,j-(i-k)}+w(k+1,i)$。发现转移的两个状态两维的差值是一样的，将 $f_{i,j}$ 变换成 $f_{i-j,i}$ 得到 $f_{t,i}=\max\limits_{k<i}f_{t,k}+w(k+1,i)$。对于每一层 $t$，从左往右扫 $i$，可以线段树做到 $\mathcal O(n^2\log n)$。发现 $i$ 在向右移动的过程中，决策点只会往前移动或者跳到 $i-1$，而且一个决策点一旦不优以后都不会更优，所以可以拿并查集和链表维护，$\mathcal O(n^2\alpha(n))$。

[★] HDU7530 树上询问

直径+路径异或和判充要。

[★] [KTSC 2024 R1] 最大化平均值（#23）

发现封闭序列的个数其实不是很多，是 $\mathcal O(n)$ 级别，再想想其实等价于删去小根笛卡尔树的一个子树。所以把笛卡尔树建出来，问题就是选一个包含一个点的连通块，使得平均值最大，这个是经典问题，可以子树归并，从 dp 发现凸性然后闵可夫斯基和也可以得到这个结论，平衡树启发式合并。

[★] 20250324 T1 / [CERC2014] The Imp 加强

首先结论是按照 $b$ 排序，这个推一推就出来了。有一个平凡的 $\mathcal O(nm)$ 的做法，但是没法优化，二分转成判定性问题。发现转移可以线段树优化，但是更好的是反悔贪心：判断在满足条件下 A 最多能买的物品个数，每次能加就加，否则反悔一个，时间复杂度 2log。

[★★] 20250324 T2 / CF1601F Two Sorts 加强（#24）

首先 $a$ 转化成 $rk$，显然 $rk$ 是比 $a$ 好求的。正常做法是 meet in the middle，这个看数据范围就能看出来，其中有关键结论 $rk(\overline{xy})=rk(\overline{x000000})+rk(\overline y)$，其中 $x,y$ 都是一个六位数。

做到这个还不够。这题棘手在于套了两个模数，所以把一个 $\bmod$ 拆开：发现我们只要算所有的 $\sum\left\lfloor\dfrac{rk_i-i}{P_1}\right\rfloor$。因为 $P_1$ 特别大，可以直接枚举值，发现可行的 $rk_i-i$ 是一个区间，而且有第二个结论：对于两个位数相同的数 $x<y$，有 $rk_x-x\le rk_y-y$，那么可以二分做到 3log，实际上可以类似于倍增逐位确定答案，那就是 2log 了。一个实现比较精巧的点就是最终要数满足条件要求是 $\min(A,B)\le lim$，其中 $A,B$ 都是关于这个数的式子，$lim$ 是常数，那么两个式子 $A,B$ 单独跑一遍 $A\le lim, B\le lim$ 得到最大可行的数 $x,y$，那么答案就是 $\max(x,y)$。

[★★★] 20250324 T3 / 「SFCOI-3」进行一个魔的除 I

？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

[★★] HDU7517 cats 的快乐 CF 刷题

这种题可能引导往平面上，或者区间 dp 优化。我们试着找点性质：如果没有限制，那么按照 $\dfrac A B$ 从大到小取。如果有限制，也是同理的。容易发现如果有三个数对 $x,y,z$，而且不满足 $\dfrac {A_x}{B_x}>\dfrac {A_y}{B_y}>\dfrac {A_z}{B_z}$，那么这三个一定会一起取走，随便证一下就出来了。所以枚举最后一个取走的点，然后倒过来取两边的链，两边单调栈合并时候就是按顺序取，因为一定是按顺序取的，所以扔到线段树上就可以 pushup 算了。

[★★] [ZJOI2018] 历史

容易发现结论，答案是每个点的 $\min(2(s_u-h_u),s_u-1)$ 之和，$s_u$ 表示子树和，$h_u$ 表示重儿子子树和，这个可以从菊花归纳而来。这个取值的形式很像树剖，更详细的，也就是一个点到根的所有点，取 $\min$ 前一项的点只有 $\log$ 个，暴力用 LCT 维护。

[★★★] [集训队互测 2022] 线段树

直接模拟肯定不行，要找点性质：如果是全局操作，那么做了 $k$ 轮之后的 $a_i$ 就是 $\sum\limits_{j=1}^i\dbinom{k}{i-j}a_j\bmod 2$，Kummer 拆一下就是一个 fwt 的形式。区间操作就没有这么好搞了，看着不太像 polylog 的东西考虑分块，$B$ 个分一块。每次给一个区间打上整体的操作 tag，边块暴力。但是每操作一个块涉及的贡献下标下界就会往前移，这样是不好的。干脆不要让他往前移太多，强制每 $B$ 个 tag 重构一次，这样只会涉及前一个块了，重构对块内的贡献也是一个 fwt 的形式，平衡一下是 $\mathcal O(n\sqrt{n\log n})$。

这题实现还是很需要注意的。首先打整块标记的时候需要实时知道的上一块最后一个位置的值，不能实时算，那么每次 rebuild 的时候提前预处理操作 $1\sim B$ 次最后位置的值。还有边块可以直接 rebuild，这样写起来会优雅很多。

[★] HDU7484 树论（一）

二元组 $(i,j),1\le i\le j\le n$ 且 $\text{lcm}(i,j)\le n$ 的量级是 $\mathcal O(n\log^2 n)$ 的，所以可以直接枚举然后扫描线。这里一种 $\mathcal O(ans)$ 的枚举方法是先枚举每个 $\text{lcm}$，质因数分解之后爆搜两个数因子的取值，还有一个稍劣但是好写的方法是枚举 $\gcd$，再枚举所有 $\dfrac{i}{\gcd},\dfrac{j}{\gcd}$​ 判断互质，跑起来不是很慢。

[★] [HNOI/AHOI2018] 毒瘤

暴力容斥是 $\mathcal O(4^{m-n}n)$ 的，建虚树可以把那个 $n$ 省掉，$2^{m-n}$ 枚举所有边中一个点的取值，那么所有值都确定了，$\mathcal O(2^{m-n}(m-n))$

[★] [SDOI2018] 原题识别-改

学习了树上莫队的简单写法，然后学会把询问复杂的东西归纳成简洁的形式，这样就可以轻松解决了。

[★] HDU7526 cats 的集合 1

关键在于发现暴力打标记下传 tag 合并的复杂度是对的，因为势能。

[★★] HDU7466 绘世之卷

• sol1 [★]

首先线段树分治，变成只加不删。发现如果数的个数 $\ge \sqrt n$ 的时候，答案一定是 $\mathcal O(\sqrt n)$ 量级的。说明如果个数 $< \sqrt n$ 的时候，我们可以暴力枚举当前集合里的数更新，否则枚举余数和商，时间复杂度 $\mathcal O(n\sqrt n\log n)$，这里线段树用非递归的常数会小很多。

• sol2 [★★]

操作分块，对于每一块考虑三种贡献：没有涉及到的元素容易 $\mathcal O(n\log n)$ 预处理，这里注意如果确定了 $\left\lfloor\dfrac{x}{y}\right\rfloor$，其中 $x$ 是定量，那么一定是 $y$ 越大答案越优。对于没有涉及到的元素和修改的元素，$\mathcal O(B\log n)$ 预处理 $B$ 个元素和前面的数的最小值，剩下 $\mathcal O(B^2)$ 种关系询问暴力删除就好了。仔细分析一下：$\mathcal O(B^2)$ 种关系需要统计个数，所以要个 bitset，但是其他的可以暴力遍历，时间复杂度 $\mathcal O(\dfrac{n^2\log n}{B}+\dfrac{nB}{\omega})$，平衡一下就能过了。

[★] QOJ8574 Swirly Sort

先特判一些 case：$k=n$ 直接做，$k=1,2$ 是经典的 $L_1$ 保序回归，时间复杂度 $\mathcal O(nk\log n)$，对于其他情况，右移操作实在难以处理，我们猜测对于 $3<k<n$ 的情况，可以实现位移 $k=3$，具体实现是：

$$\tt \underline{OXXXXAB}C\underline{XXXX}\\ \tt \underline{XOXXXX}A\underline{CBXXX}\\ \tt OXXXXCABXXXX$$

容易发现 shift 了一次，根据这个，我们可以得出更强的引理：

• 引理 1：对于 $3<k<n$，如果 $k$ 是偶数，那么可以 shift 到所有排列；如果是奇数，那么如果原排列的逆序对为奇数，能到达所有逆序对为奇数的排列，否则能到达所有排列。

首先，对于一个起始排列 $s$ 要到达最终排列 $t$，我们建立数组 $p_i=j(t_i=p_j)$，$s$ 的每次 shift 也对应 $p$ 的每次 shift，又因为 $k=3$ 的 shift 不会改变排列奇偶性，所以如果 $p$ 逆序对是奇数，那么一定会有一对数不能符合要求。因为两个排列复合之后的排列，逆序对奇偶性也是复合的，所以只能从相同奇偶性到达。而 $k$ 为偶数的时候可以切换奇偶性，所以能到达全部排列。

剩下的就好做了，特判一下 $k$ 为奇数而且逆序对为奇取值是排序之后最小的相邻数之差。

[★] [PKUWC2018] Minimax

好像是线段树合并板题，忘了。

[★] [CERC2017] Intrinsic Interval

如果对普通的这个区间计数，非常经典：一种是统计 $\max-\min=r-l$；还有一种是把值域相邻的数连边，$[l,r]$ 合法就是构成的导出子图是一条链，只要维护 $|V|-|E|$ 就好了。拓展的这题上，倒着扫描线 $r$，每次就是查询一个前缀的历史最小答案的最小值，需要支持区间更改 $|V|-|E|$，同时对于区间最小值且 $=1$ 的位置，以右端点为 $r$ 下放标记，这个推一下就好了。

[★] [WC2022] 秃子酋长

难点在于想到回滚莫队，想到了就好做了：每次到一个新的块，右端点倒着扫，这样维护一个链表就可以快速得到前驱后继，左端点暴力删然后撤销。注意这里为了让常数小一点要全局动态维护指针 $l,r$，而不是每个块重构一遍。

[★] HDU7536 最佳选手

判断一个选手能不能成为最佳选手，先把与这个选手有关的比赛分都给他，得到最大的得分 $s$。剩下的可以建立图论模型：有比赛的两个人 $u,v$ 之间，如果 $u,v$ 只能其中一个人小于 $s$，那么两点连边；否则给能独立 $<s$ 的点连一个自环，能成为最佳选手的条件就是每个连通块边数 $\ge$ 点数，对最大得分排个序扫描线就可以用并查集维护了。

[★★] [BJOI2019] 送别

把整个图切分成若干个连通块，每个连通块走过的边缘就是一个环，我们需要支持快速合并环，分裂环并且能查询环上两点的距离，这个可以用平衡树维护。有一个小巧思就是因为直接维护边是不好搞的，我们把每个点的四个角都建一个点，根据两点有没有边来调整对应的四个角之间的连边方向：

发现对一道墙的修改就是交换了两个点的前驱后继，可以根据两个点是否在一个平衡树之内判断，然后就是按节点分裂，和一些细节。

[★] CF765F Souvenirs

[★★★] [Ynoi2002] Adaptive Hsearch&Lsearch

上面那一题，我们尝试找出所有支配对，一种普通的办法是像第一篇题解那样倍增值域去找，但是可以换一个类似的角度：枚举支配对靠后的点 $i$，假设我们只考虑 $j<i$ 且 $a_j>a_i$（剩下的是对称的），只要对于所有 $0\le 2^k\le V$，找到值域在 $[a_i+2^{k-1},a_i+2^k)$ 的 $j$ 中最大的 $j$ 就好了，随便证明都可以。

试着扩展到区间平面最近点对。我们对平面按照网格长度为 $2^k$ 分块，每次只要找到每个块内相邻 $R$ 个点对和相邻块合并起来，按照编号排序相邻的 $R$ 个点对，其中 $R$ 是一个常数，取 $7$ 左右，大概的构造可以看一下讨论区的 hack，原理就是对于一个固定的 $k$，构造一个块内的 $7$ 个点，使得这 $7$ 个点在划分成 $2^{k-1}$ 的时候不在一个块。然后就是二维数点，因为支配对数量太大了所以分块平衡一下，时间复杂度 $\mathcal O(nR\log n\log V +q\sqrt n)$​。

[★] HDU7319 String and GCD

莫反一下 $i,j$ 的贡献变成 $\sum\limits_{d|i,j}\varphi(d)$，直接在 border 树 dfs 暴力修改。

[★] [CTSC2018] 暴力写挂

见「学习笔记：点分治（树） & 边分治（树）」。

[★] [九省联考 2018] IIIDX

好像是从 Hall 定理的角度来讲会好一点（？）但是我没看太懂，先咕咕了。做法就是贪心的时候维护 $f_i$ 表示只考虑 $\ge i$ 的限制，$\ge i$ 的数还能用几个。发现判定可行只要前缀 $\min$​ 就好了，线段树二分。

[★] [BJOI2018] 链上二次求和

线段树板题。

[?] QOJ9222 Price Combo

[?] QOJ868 Friendship Circles

QOJ5738 Square Sum

[KTSC 2024 R1] 警察与小偷

HDU7505 纠缠点对

HDU7502 数字加减

QOJ9605 新生舞会