题解
数学推导杂项
题面
给定 $n$ 个点 $(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)$ ，求出 $\sum_{i=1}^{n}\sum_{j=i+1}^{n}{((x_i-x_j)^2+(y_i-y_j)^2)}$ 。
$2\le n \le 10^5,|x| \le 10^5,|y| \le 10^5$ 。
题解
简单题。对于 $x$ ，式子变成 $\sum_{i=1 …
Jayun 发布于 2023-11-01 13:42:47
11
并查集吉司机线段树（势能分析线段树）
题面
有 $n$ 个容器，从最高层到最底层分别编号为 $1,2,\cdots,n$ 。
现在会在这些容器中倒上一些香槟，当第 $i$ 层容器倒满时，多余的香槟会流到第 $i+1$ 层中，如果第 $n$ 层容器也满了香槟就会流到外面去。第 $i$ 层容器的容量为 $a_i$ ，不保证 $a$ 递增。
你需要实现下面两种操作 $q$ 次：
往某一个编号为 $x$ …
Jayun 发布于 2023-11-01 13:28:08
00
枚举区间动态规划（区间 DP）朴素模拟
题意
给一段程序：
int qsort(int L, int R) {
if (L >= R) return 0;
int i = L, j = R;
int x = Random.Next();
int x0 = A[x];
assert(L <= x && x <= R);
while (i < j) {
while (A[i] < …
Jayun 发布于 2023-11-01 07:20:17
00
博弈树形动态规划（树形 DP）二分答案
题意
给定两个人的树上博弈规则。小 N 初始时在节点 $S$ ，小 Y 需要通过一些操作“强迫”小 N 最后到达节点 $T$ 。小 N 想要让小 Y 的操作尽量多，而小 Y 希望自己的操作尽量少。求解两人都采取最优决策时，小 Y 的操作次数。 每一轮中操作如下：
小 Y 可选的操作有：恢复一条小 N 删除的边 ；或者删除一条边；或者跳过这次操作（不计入答案）。
小 N 接下来执行：如果 …
Jayun 发布于 2023-10-31 21:21:25
00
李超线段树
题目描述
要求在平面直角坐标系下维护两个操作：
在平面上加入一条线段。记第 $i$ 条被插入的线段的标号为 $i$ 。
给定一个数 $k$ ，询问与直线 $x = k$ 相交的线段中，交点纵坐标最大的线段的编号。
强制在线。
题解
李超树板题。在点上维护线段。
代码
const int N = 100005;
const int mod = 39989;
const double …
Jayun 发布于 2023-10-31 15:59:30
00
李超线段树
Escape Through Leaf
题面
有一颗 $n$ 个节点的树（节点从 $1$ 到 $n$ 依次编号），根节点为 $1$ 。每个节点有两个权值，第 $i$ 个节点的权值为 $a_i,b_i$ 。
你可以从一个节点跳到它的子树内任意一个节点上。从节点 $x$ 跳到节点 $y$ 一次的花费为 $a_x\times b_y$ 。跳跃多次走过一条路径的总费用为每次跳 …
Jayun 发布于 2023-10-31 15:51:30
00
区间动态规划（区间 DP）
题面
法阵由从左至右 $n$ 道魔力屏障组成，每道屏障有一个临界值 $a_i$ ，如果它承受攻击的魔力值 $>a_i$ ，屏障将会破碎，它所承受的魔力攻击将在魔力值减半后（向下取整）继续向右移动，否则该攻击会被该屏障完全拦截，停留在屏障前，屏障的临界值不会减少。当两次攻击相遇时，两次攻击会叠加形成新的攻击，新的攻击的魔力值为两次攻击魔力值之和，新的攻击会继续向右移动。小 Z 可以在法 …
Jayun 发布于 2023-10-31 14:12:43
00
凸包斜率优化动态规划（斜率优化 DP）几何基础基础分治
题意
在线进行 $n$ 个操作：
把向量 $(x,y)$ 插入到平面内；
给一个向量 $(x,y)$ ，问平面内第 $l$ 个到第 $r$ 个向量之间中的一个向量与该向量的点积最大值。
$n\leq 3\times10^5$ 。
口胡
挺酷炫的。考虑到查询操作的 $x,y$ 相当于给了个直线斜率。那么解肯定在 $[l,r]$ 的凸包上，那么线段树每个点维护一个凸包（ …
Jayun 发布于 2023-10-31 11:55:53
00
WQS 二分决策单调性优化动态规划（决策单调性优化 DP）
题解
这里用了 WQS 二分，二分队列做法。
const int N = 5e5 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c …
Jayun 发布于 2023-10-30 22:01:54
00
重链剖分（HLD）深度优先搜索（DFS）
题意
一棵 $n$ 个节点的树，第 $i$ 个点值为 $a_i$ 。 $q$ 次操作，每次操作要么单点修改；要么给出 $k$ 个数，查询这 $k$ 个点中任意两点的简单路径上的所有点的点值总和。
$n,q\leq10^5,\sum k\leq10^6$
口胡
询问先按 dfs 序排序，然后从第 1 个点往后合并（统计到 lca 的答案）。树剖维护。
然后看答案验证发现错了。 …
Jayun 发布于 2023-10-30 19:59:19
00