2020 May Records | fa

菜鸡 fa_555 会把一些动态简要地记在这里。主要还是留给自己以后看的。

所有代码不保证包括无关紧要的部分

[TJOI2013]松鼠聚会

problem

给定平面上的 $n \ (0 \le n \le 10^5)$ 个点 $(x, y) \ (-10^9 \le x, y \le 10^9)$，选出一个点使得其他所有点到这个点的切比雪夫距离之和最小，求出这个最小值。

solution

有结论：

将所有点 $(x,y)$ 修改为 $(x + y, x − y)$ 后，原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离；
将所有点 $(x,y)$ 修改为 $(\frac{x + y}2, \frac{x - y}2)$ 后，原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。

于是可以推式子。假设已经将所有点转化为曼哈顿坐标系中的点，且已按照 $x$ 坐标升序排序，对于一个点 $(x_i, y_i)$，有

$\begin{align} \sum_{j = 1}^n{|x_i - x_j|} &= \sum_{j = 1}^i{(x_i - x_j)} + \sum_{j = i + 1}^n{(x_j - x_i)} \\ &= i x_i - \sum_{j = 1}^i{x_j} + \sum_{j = i + 1}^n{x_j} - (n - i) x_i \\ &= (2i - n) x_i + S_n - 2 S_i \end{align}$

其中 $S_i = \sum_{j = 1}^i{x_i}$。$y$ 坐标同理。

这玩意排序之后 $O(n)$ 整就行了，总复杂度是 $O(n \log n)$ 的。

[HNOI2010]弹飞绵羊

solution

考虑暴力，维护每个位置弹到哪个位置、需要几步弹飞。这样做修改是 $O(n)$ 的，查询是 $O(1)$ 的。我们要想办法平衡两者的复杂度。

考虑分块，对于每个位置维护弹到块外的哪个位置、需要几步弹出块。这样修改和查询都是 $O(\sqrt n)$ 的，总复杂度 $O(n \sqrt n)$。

code

教主的魔法

区间带修求排名，参见数列分块入门 2。

Dynamic Rankings

区间带修求第 k 小模板题。

区间可以看作 $\log$ 棵线段树和 $\log$ 棵线段树作差。可以通过树状数组套主席树实现。空间 $O(n \log^2 n)$，时间 $O(n \log n)$。

code

CF1433N Monopole Magnet

problem

给定一个 $n$ 行 $m$ 列 $(1 \le n, m \le 1000)$ 的棋盘，其中每个格子被染成了黑色或白色。你需要在棋盘格子里放置一些单极磁铁。每个格子可以放任意多个磁铁。

定义单极磁铁的吸引：任选一对 N 磁铁和 S 磁铁，如果它们处在同一行或同一列中且不处在同一格中，则 N 磁铁向 S 磁铁的方向靠近 1 格。

磁铁的放置需要满足以下要求：

每行每列都至少要有一个 S 磁铁。
对于每个黑色格子，必须有 N 磁铁经过若干次吸引操作后能够到达该格。
对于每个白色格子，必须有 N 磁铁经过任意次吸引操作后不能到达该格。

求最少的 N 磁铁的个数或判断无合法方案。

solution

考虑黑色格子直接放满 S 磁铁，随便一想发现有解的情况就是求连通块个数，重点在于判断有无合法解。

再一想发现有且仅有这两种情况无解：

同一行或同一列的两个黑色格子中间有白色格子。
某行没有黑色格子异或某列没有黑色格子。如果有行和列都没有黑色格子，那么 S 磁铁可以放在它们的交点处。

~~（情况 1 限制 23）和（情况 2 限制 1）感觉就是两道题强行拼起来的~~

code

CF1344D Résumé Review

problem

给定一个长为 $n \ (1 \le n \le 10^5)$ 的序列 $a \ (1 \le a_i \le 10^9)$，构造序列 $b$ 满足

$\forall 1 \le i \le n, \ 0 \le b_i \le a_i$
$\sum_{i = 1}^n{b_i} = k$

并最大化 $\sum_{i = 1}^n{b_i (a_i - b_i^2)}$。输出任意一组解。

solution

这里大部分抄了 CF 官方题解。

如果我们对于某个 $b_i$ 从 $x - 1$ 自增到 $x$，那么总价值将会变化

$\Delta_i(x) = x (a_i - x^2) - (x - 1)(a_i - (x - 1)^2) = a_i - 3x^2 + 3x - 1$

这个函数在 $x \ge 1$ 时单调减。

如果初始时令 $b_i = 0$，贪心地增加当前最佳的 $b_i$，那么就能获得最优解，然而至少 $O(k \log n)$ 的复杂度是我们所不能接受的。

我们可以二分某个 $A$，使得使得 $\Delta_i(x_i) \ge A$ 的 $\sum{x_i}$ 恰好等于 $k$。check 时求 $x_i$ 可以通过求根公式或另一次二分答案得到。总复杂度是 $O(n \log k)$ 或 $O(n \log^2 k)$ 的。

code

洛谷 / Codeforces

扩展 KMP 算法（Z 算法）

咕咕咕

一般图最大匹配（带花树算法）

solution by Fuyuki

我完全无法复述得更好了。

code

洛谷板题数据非常水，一定要去 UOJ 测，一定要去 UOJ 测，一定要去 UOJ 测

[WC2016]挑战NPC

一般图最大匹配的应用不多，只找到了这一个题。

problem

有 $n \ (1 \le n \le 3m)$ 个球和 $m \ (1 \le m \le 100)$ 个筐子，每个筐子最多可以装三个球。有 $e \ (1 \le e \le nm)$ 个条件，条件 $(u, v)$ 表示编号为 $v$ 的球可以放进编号为 $u$ 的筐子中。

每个球都必须放进一个筐子中，称放有不超过 $1$ 个球的筐子为半空的。求半空的筐子最多有多少个，并输出一个最优方案。

solution

这题的思路非常妙。建图方式是这样的：对每个篮子拆成 $3$ 个点，在这 $3$ 个点之间两两连边，在对 $e$ 个条件连 $3e$ 条边。为什么这样是对的？

分别考虑每个篮子放入 $0, 1, 2, 3$ 个球的情况。这时它们对答案的贡献分别是 $1, 2, 2, 3$，而我们希望它们的贡献分别是 $1, 1, 0, 0$。作差得到 $0, 1, 2, 3$，因此这样统计到的贡献减去球的个数就是正确答案！

注意一个问题，最终的匹配中要优先匹配球再匹配筐，否则会输出错误的方案。~~因为这个卡了一晚~~

code

[PKUWC2018]Slay the Spire

由于 fa_555 非常喜欢玩 Slay the Spire，他跑来写（抄）了这题。但是这题和游戏一点关系也没有。

problem

有 $n$ 张强化牌 $a_i$ 和 $n$ 张攻击牌 $b_i$，每张牌有一个 $[1, 10^8]$ 之间的权值，每张强化牌能使所有攻击牌的权值乘上这张强化牌的权值。

任意摸 $m$ 张牌，以最优策略出 $k$ 张牌，求造成伤害的期望乘以 $\binom {2n}m$。答案模 $998244353$。

solution - 转化

首先发现要求的这个东西其实就是所有情况下造成的伤害总和。

考虑如果现在已经选定了 $m$ 张牌，最优策略是什么？

如果已经确定用 $x$ 张强化牌和 $y$ 张攻击牌，那么肯定是先用权值最大的 $x$ 张强化牌，再用权值最大的 $y$ 张攻击牌。
在保证至少出一张攻击牌的情况下，尽量多出强化牌一定不会使答案更劣。
- 这个不必严谨地推式子，只要考虑强化牌至少能使权值最大的攻击牌的权值翻倍，不劣于选其他任何攻击牌即可。

solution - 预处理

设 $f_{i, j, 0}$ 表示前 $i$ 张强化牌中选择 $j$ 张且第 $i$ 张被选中的所有情况下这 $j$ 张牌的乘积之和；$g_{i, j, 0}$ 表示前 $i$ 张攻击牌中选择 $j$ 张且第 $i$ 张被选中的所有情况下这 $j$ 张牌的和之和。同时设 $f_{i, j, 1} = \sum_{k = j}^i{f_{k, j, 0}}, \ g_{i, j, 1} = \sum_{k = j}^i{g_{k, j, 0}}$，那么可得

$\begin{align} f_{i, j, 0} &= a_i \cdot f_{i - 1, j - 1, 1} \\ f_{i, j, 1} &= f_{i, j, 0} + f_{i - 1, j, 1} \\ g_{i, j, 0} &= b_i \cdot \binom{i - 1}{j - 1} + g_{i - 1, j - 1, 1} \\ g_{i, j, 1} &= g_{i, j, 0} + g_{i - 1, j, 1} \end{align}$

solution - 统计答案

分两种情况：

其一，$m$ 张牌中强化牌的数量小于 $k - 1$

此时必然是出所有强化牌，然后出权值最大的一些攻击牌。

枚举强化牌有 $i$ 张、选中的最后一张攻击牌是第 $j$ 张。

如果要保证最优方案是这 $k$ 张牌，剩下的 $m - k$ 张牌还需要满足全部都是攻击牌，并且都在第 $j$ 张之后。

此时对答案的贡献为 $f_{n, i, 1} \cdot g_{j, k - i, 0} \cdot \binom{n - j}{m - k}$。

其二，$m$ 张牌中强化牌的数量大于等于 $k - 1$

此时必然是出权值最大的 $k - 1$ 张强化牌，然后出权值最大的一张攻击牌。

枚举选中的最后一张强化牌是第 $i$ 张，选中的攻击牌是第 $j$ 张。

如果要保证最优方案是这 $k$ 张牌，剩下的 $m - k$ 张牌还需要满足所有强化牌都在第 $i$ 张之后，所有攻击牌都在第 $j$ 张之后。

此时对答案的贡献为 $f_{i, k - 1, 0} \cdot b_j \cdot \binom{2n - i - j}{m - k}$。

code

它被卡常了，并过不去。

GSS5 - Can you answer these queries V

problem

给定一个长为 $n$ 的序列 $a$，每次查询左端点在 $[l_1, r_1]$ 之间，右端点在 $[l_2, r_2]$ 之间的最大子段和。不保证两个区间不相交。

solution

首先考虑两个区间 $[l_1, r_1], [l_2, r_2]$ 不相交或只在端点处相交 $(r_1 \le l_2)$ 的情况，发现答案就是右边区间的最大前缀和减去左边区间的最小前缀和。记这个答案为 $f([l_1, r_1], [l_2, r_2])$。

那么对于相交 $(l_2 < r_1)$ 的情况也就很容易讨论了：答案是 $[r1, l2]$ 的最大子段和、$f([l_1, r_1], [r_1, r_2])$、$f([l_1, l_2], [l_2, r_2])$ 三者取最大值。

code

只在端点相交的情况两种情况都可以讨论，代码放在了第二种情况里。

李超树

学习笔记在这

[CEOI2017]Building Bridges

solution

设 $f_i$ 为将第 $1$ 根柱子和第 $i$ 根柱子相连的最小代价，令 $S_i = \sum_{j = 1}^i{w_j}$，则

$\begin{align} f_i &= \min_{j = 1}^{i - 1}{ \left \{ f_j + \sum_{k = j + 1}^{i - 1}{w_k} + (h_i - h_j)^2 \right \} } \\ &= \min_{j = 1}^{i - 1}{ \{ f_j + S_{i - 1} - S_j + h_i^2 - 2 h_i h_j + h_j^2 \} } \\ &= S_{i - 1} + h_i^2 + \min_{j = 1}^{i - 1}{ \{ f_j - S_j + h_j^2 - 2 h_i h_j \} } \end{align}$

令 $k = -2h_i, b = f_j - S_j + h_j^2$，则可以用李超树维护。

CDQ 分治少一个 $\log$ 但我不会，不过李超树小常数跑得好像更快（

code

作诗

problem

给定长为 $n \ (1 \le n \le 10^5)$ 的序列 $a$ 和 $m \ (1 \le m \le 10^5)$ 次询问，每次询问 $a_{l \dots r}$ 中出现次数为正偶数的数字个数。

solution

长得跟蒲公英似的（？）

考虑分块，设 $s_{i, j}$ 表示第 $i$ 块开头到序列结尾数字 $j$ 的出现次数，$f_{i, j}$ 表示第 $i$ 块到第 $j$ 块的答案。

这样时间复杂度是 $O(n \sqrt n) - O(\sqrt n)$ 的；空间复杂度是 $O(n \sqrt n)$ 的。

code

LCT

学了学 LCT，也没啥好说的，放个板子吧。

namespace LCT {
  std::bitset<100003> rev;
  int z[100003], s[100003], fa[100003], ch[100003][2];

  inline bool get(int p) {
    return ch[fa[p]][1] == p;
  }

  inline bool notRt(int p) {
    return ch[fa[p]][0] == p || ch[fa[p]][1] == p;
  }

  inline void assign(int p) {
    if (!p) return;
    std::swap(ch[p][0], ch[p][1]);
    rev.flip(p);
  }

  inline void pushup(int p) {
    s[p] = s[ch[p][0]] ^ s[ch[p][1]] ^ z[p];
  }

  inline void pushdown(int p) {
    if (rev[p]) assign(ch[p][0]), assign(ch[p][1]), rev.reset(p);
  }

  void update(int p) {
    if (notRt(p)) update(fa[p]);
    pushdown(p);
  }

  inline void rotate(int p) {
    int f = fa[p], g = fa[f], k = get(p), r = ch[p][!k];
    if (notRt(f)) ch[g][get(f)] = p;
    ch[f][k] = r, ch[p][!k] = f;
    fa[r] = f, fa[f] = p, fa[p] = g;
    pushup(f), pushup(p);
  }

  void splay(int p) {
    update(p);
    for (int f; notRt(p); rotate(p))
      if (notRt(f = fa[p])) rotate(get(f) != get(p) ? p : f);
  }

  void access(int p) {
    for (int q = 0; p; p = fa[q = p])
      splay(p), ch[p][1] = q, pushup(p);
  }

  inline void makeRt(int p) {
    access(p), splay(p), assign(p);
  }

  int findRt(int p) {
    access(p), splay(p);
    while (ch[p][0]) pushdown(p), p = ch[p][0];
    splay(p);
    return p;
  }

  inline void link(int p, int q) {
    makeRt(p);
    if (findRt(q) != p) fa[p] = q;
  }

  inline void cut(int p, int q) {
    makeRt(p);
    if (findRt(q) != p || ch[q][0] || fa[q] != p) return;
    fa[q] = ch[p][1] = 0;
    pushup(p);
  }

  inline void split(int p, int q) {
    makeRt(p), access(q), splay(q);
  }
} // LCT

其中 update(p) 有非递归写法：

int top, st[100003];

void update(int p) {
  st[top = 1] = p;
  while (notRt(p)) st[++top] = p = fa[p];
  while (top) pushdown(st[top--]);
}

problem

$n \ (1 \le n \le 10^5)$ 个点的树，每个结点有一个颜色。$m \ (1 \le m \le 10^5)$ 次操作，每次修改一个结点的颜色或查询每条链上的颜色段数。

solution

这题维护信息的方式比较怪异（

记录每个点代表的区间最左端的颜色 lc、最右端的颜色 rc、该点的颜色 c 和颜色分界点的个数 s。注意统计某点的答案时要先 pushdown 一下来更新儿子的信息。

assign 的时候记得把两边儿子的最左端和最右端分别换一下。

code

奶牛浴场 / 球场 Cricket Field

最大子矩形 / 正方形的 $O(s^2)$ 版本，其中 $s$ 为障碍物数量。

code

奶牛浴场 / 球场 Cricket Field