本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-31 09:07:04

例题 P4198 楼房重建

题意即，求整个序列中前缀最大值的数量。

考虑线段树能否维护。首先维护一个区间答案，然后考虑怎么动态维护。

线段树动态维护的方法，就是考虑左右区间的贡献，得到一个大区间的答案，然后向上递归。

那么，在这个题目里，左右区间的贡献怎么计算？

首先显然，右对左是没有贡献的。左对右的贡献，看起来很不好计算。我们来分类讨论：

• 左极值如果大于右极值，那么右边答案就是零

• 左极值如果小于右极值，这时候还不好得出结论。我们继续分讨：

• 左极值大于右左区间的极值，那么右左区间答案是零，我们在右右区间上递归

• 否则，我们考虑：既然左极值小于右左区间极值，那么右右区间受它的的影响，一定是不如受右左区间的影响的。换句话说，右右区间受不到左极值的影响。这时候，右区间的答案，就是右右区间的答案加上右左区间上递归得到的答案。

在这道题中，我们为了计算左右区间之间的贡献，需要另外做一次递归。换句话说，我们的 pushup 是 $O(\log n)$ 的。这样，一次点修的复杂度 $O(\log^2 n)$。

例题 [FJOI2016] 神秘数

题意为：求出最小的不能被区间 $[l, r]$ 子集的和表示出来的数。

我们先想一下暴力怎么做。

我们维护一个 $p$，表示 $[1, p)$ 的数都能表示出来。初始地，$p = 1$。

我们考虑怎么表示出 $p$。显然，能表示出 $p$，当且仅当存在 $u \le p$。如果找得到这样的 $u$，$p\gets p + u$。否则，答案就是 $p$。

我们考虑怎么加速。

首先更新以下策略：每次找小于等于 $p$ 的数之和 $q$。如果这个和大于等于 $p$，由于所有的数都是小于 $p$ 的，我们显然可以表示出 $q$ 以内的所有数。此时 $p \gets q + 1$。否则,我们同样能得出答案 $p$。

这个过程是 $O(\log V)$ 的，但很松。

我们再审视一下这个问题：找小于等于 $p$ 的数之和，这就是主席树板子，在 $O(\log V)$ 的时间可以做到。于是整体时间是很松的 $O(\log^2 V)$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-31 15:25:13

题意明确。

$$ \begin{aligned} \mathrm{圆柿} &= \sum\limits_{p \in \mathrm{primes}}\sum\limits_{i=0}^n\sum\limits_{j=0}^m [(i, j) = p] \ &= \sum\limits_{p \in \mathrm{primes}}\sum\limits_{i=0}^n\sum\limits_{j=0}^m\sum\limits_{d\mid (i,j)} \mu(d) \ &=\sum\limits_{p\in\mathrm{primes}}\sum\limits_{d=1}^{\min(n,m)}\mu(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^m [d\mid i][d \mid j] \ &= \sum\limits_{p\in\mathrm{primes}}\sum\limits_{d=1}^{\min(n, m)}\mu(d)\lfloor\dfrac n {pd}\rfloor\lfloor\dfrac m {pd}\rfloor \end{aligned} $$

最开始只得到了这个 $O(Tn)$ 的做法，爆零。但是可以再优化一下。设 $u = pd$，则

$$ \begin{aligned} 圆柿 = \sum\limits_{u=1}^{\min(n, m)}\lfloor{\dfrac n u}\rfloor\lfloor\dfrac m u\rfloor\sum\limits_{d\mid u}\mu(\dfrac u d) \end{aligned} $$

然后惊奇地发现后面的柿子可以 $O(V)$ 预处理！

于是本题就用优雅的 $O(V + T\sqrt n)$ 复杂度做完了

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-02 20:47:40

对顶堆可以处理动态第 $k$ 大等问题（$k$ 是常数）。

如果不用对顶堆，我们可以用平衡树解决这个问题，但是常数一般比前者大 2~3 倍（我的实现）。

对顶堆实际上是两个堆，一个大根，一个小根。每个堆自己的单调性是显然的，而我们同样要维护堆之间的单调性：小根堆的最小是大于大根堆的最大的。

就算这样又怎么样？没法怎么样。为了快速得到第 $k$ 大，我们需要保证大根堆里头只有 $k - 1$ 个元素。这样，每一次我们取小根堆的头就可以了。

如果要维护动态中位数，也是可以的，只需要保证两个根的大小差是不超过 1 的即可，中位数就是较大的堆的根。

有人将对顶堆形容为一个沙漏，让人印象很深。但是，如果看成是两个梯形躺在地上，左边是大根堆，右边是小根，中间是分界线，而小根的顶大于大根的顶，应该更形象。

于是我们就维护出了动态第 $k$ 大。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-04 16:09:08

题意还是比较明确的。首先我们需要知道异或的两个性质：$a\oplus a = 0$ 与 $a\oplus 0 = a$。

遇到没思路的时候，先来看几个栗子：

• $(1000)_2 + 1 = (0001)_2$，$k$ 从 $(3)$ 变成 $(0, 3)$，那么 $f(u + 1) = f(u) \oplus a_0$。

• $(0011)_2 + 1 = (0100)_2$，$k$ 从 $(0, 1)$ 变成 $2$，$f(u + 1) = f(u) \oplus a_0 \oplus a_1 \oplus a_2$。

• $(1111)_2 + 1 = (10000)_2$，$k$ 从 $(0, 1, 2, 3)$ 变成 $(4)$，$f(u + 1) = f(u) \oplus a_0 \oplus a_1 \oplus a_2 \oplus a_3 \oplus a_4$。

观察到：如果 $u + 1$ 进了 $k$ 位，就有 $f(u + 1) = f(u)\oplus \sigma_k$，其中 $\sigma_k = \bigoplus\limits_{i=0}^k a_i$，即 $a$ 的前缀异或和。由题意，$f(u + 1) = f(u)$，故 $\sigma_k = 0$。然后考虑怎么统计答案。

如果 $u + 1$ 进了 $k$ 位，就意味着它的低 $k$ 位全都是 $1$，那么就剩下 $n - k - 1$ 位可以选，也就是 $2^{n - k - 1}$ 种方案。

换句话说，每一个 $\sigma_k = 0$ 的 $k$，都会产生 $2^{n - k - 1}$ 的贡献。 题意中让我们输出二进制表示，于是我们将答案的第 $n - k - 1$ 位置一即可。

最后考虑一个边缘情况：$\sigma_n = 0$，即样例二。这种情况特判，将最终答案加一即可。

赛时码：

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int res[N];

int main (void)
{
    int t;

    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cin >> t;
    while (t--) {
        int n, sum = 0, high = 0;

        cin >> n;
        for (int i = 0; i <= n; i++) {
            int v;
            cin >> v;
            if ((sum ^= v) == 0 && i < n) res[n - i - 1] = 1, high = max (high, n - i - 1);
        }

        if (!sum) {
            int q = 0;
            while (res[q]) res[q++] = 0;
            res[q] = 1;
        }
        for (int i = high; i >= 0; i--) cout << res[i];
        cout << '\n';
        for (int i = 0; i <= high; i++) res[i] = 0;
    }
    return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-07 16:53:22

我们首先用重心做根，那么有一个结论：将非根点 $u$ 子树内的边断开，不可能让 $u$ 是重心，用树的重心性质比较好证。

然后，我们设被删掉的另一部分的大小为 $m$，则 $2h_u \le n - m$ 且 $2(n - m - s_u) \le n - m$，化简得到： $m \in [n - 2s_u, n - 2h_u]$。

考虑 $m$ 是怎么来的。我们设 $(w, v)$ 是被删掉的边（$v$ 更深），两种情况：

• $v$ 和 $u$ 在同一条链上，那么 $m = n - s_v$
• 否则，$m = s_v$

我们将所有 $s$ 放到树状数组中，然后在 DFS 的过程中加入 $n - s_v$，DFS 结束时候删除，于是就可以得到答案。

怎么处理子树内的边？我们维护另一棵树状数组，然后计算进入进出子树的差值即可。

根的贡献需要特殊计算，我们分两种情况：

• 删掉的 $v$ 在重儿子子树上，那么要求次重链的长度 $2h' \le n - s_v$
• 否则，$2h \le n - s_v$

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-09 21:11:28

做的大概是第二到第三道基环树的题，明显对环的一系列操作不熟悉。

我们知道，作为有向图，要做到两点互相连通，一定是形成一个环。同时显然，题目中所给的是一个基环森林，我们需要把每个基环树断成链，然后把它们首尾相接就可以了。具体断哪条边，需要在环上 DP。

按照基环树的一般策略，把环当作根，然后对环上每一个点跑树形 DP，把重链抽出来显然是最优的。我们可以计算其他点权和，计入贡献。

然后我们考虑环上怎么处理。对于每一个点，有两种情况：断掉 $u$ 到环上前驱 $v$ 的边，使环变成一个链；或者是断掉 $v$ 的重儿子，维护当前形态。

分讨转移即可。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-06 19:13:00

本题就是在基环树上找直径。

我们可以先找出不带环时的直径。因为边权非负，我们可以用两次 DFS 或者树形 DP。

然后考虑带环的时候，直径会怎么变化。由于只有一个环，直径一定分为两个部分：树边组成的与环上的，设它们的交界点为 $p$ 与 $q$，那么总直径长为 $f(p) + f(q) + \sigma(p,q)$。

但是，找这个最大值同样是无法接受的，这才是本题的难点。我们将环拆成两倍长度的链，于是问题转化成：在这个链上找 $f(i) + f(j) + \sigma(i, j)$ 的最大值，$\text{s.t.} \space \lvert j - i + 1\rvert \le n$。

这可以用单调队列。以上。

好题！

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-08 16:55:52

分数规划，$\dfrac{\sum\limits_{u \in S} F_u}{\sum\limits_{e \in E} T_e} \ge c$，即 $\sum\limits_{u\in S} F_u \ge c\sum\limits_{e\in E} T_e$，即 $\sum\limits_{u\in S}F_u - c\sum\limits_{e\in E}T_e \ge 0$，即 $\sum\limits_{e\in E} cT_e - \sum\limits_{u\in S} F_u \le 0$

于是就变成判断负环，其中，每一条边 $(u,v)$ 的边权就是 $cT_e-F_u$。

用 SPFA + 二分可做。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-09 13:04:55

排列 DP 的一般状态是：$f(i, j)$ 代表 $1$ 到 $i$ 的排列中，目标组合已经有了 $j$ 个。

那么套用到本题就是：$f(i, j)$ 代表 $1$ 到 $i$ 的排列中，已经有了 $j$ 个逆序对。

我们很容易注意到，由于 $i$ 在 $1$ 到 $i - 1$ 的排列中是最大的，我们无论将 $i$ 插入到哪里都会让整个序列的逆序对数量加上这个位置后面的数字数。

形式化地，设 $i$ 被插入到 $p$ 的位置，其中 $p\in [0,i - 1]$，那么，逆序对将会比原来多 $i - p - 1$ 个。也即，$f(i, j) = \sum\limits_{p=0}^{i-1}f(i-1, j - i + p + 1)$。规约一下，得到

$$f(i, j) = \sum\limits_{k=\max{0,j-i+1}}^{j} f(i-1, k)$$

这个转移就是 $O(n)$ 的，于是整体 $O(n^2k)$，显然不行。

我们考虑：等号右边是一个求和，而且求和区间随着 $j$ 的移动而单增。那么，我们可以维护一个前缀和。

我们维护 $\sigma(j) = \sum\limits_{k=0,j-i+1}^j f(i-1,k)$，那么在转移的时候，有 $f(i,j) \gets \sigma(j)$，随后 $\sigma(j)$ 更新上 $f(i, j)$ 的值。

此时如果 $j - i + 1$ 移动，我们就需要减去移动的这一段空窗，即 $f(i - 1, j - i + 1)$。

典型的黄题比绿题难……

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-10 17:50:00

本题的转移方程显然

$$f(i) = \max\limits_{0 \le j \lt i} f(j) + 1, \space \text{s.t.} \space \max a_j \le \min a_i$$

如果没有后面的限制，这玩意儿就根本不是个动态规划，因为我们可以证明此时 $f(i) = f(i-1) + 1$。但是有了后面的限制之后，问题棘手了一些，因为转移变成了 $O(n)$ 的，难以接受。

我们可以考虑 CDQ 分治：先对左区间进行处理，然后考虑对右边的影响。只考虑影响的时候，由于本题显然有单调性，我们可以将左右区间排序，左区间依据 $\max a_i$，右区间依照 $a_i$。

这样，我们用双指针（CDQ 分治标配）扫描一边，利用单调性，可以做到 $O(n\lg n)$（$\lg n$ 来自树状树组）。加上排序 $o(n\lg n)$，整体复杂度是 $O(n \lg^2 n)$，不错。

总体上看，CDQ 分治首先利用分治的思想，让我们只需要考虑左区间对右边的影响（因为左边与右边单独的两个区间，是另外的两个问题）。这个时候，我们就可以利用问题的单调性，加上双指针与一些数据结构（常见树状树组）就能解决问题。