题意：

给 $n$（$\le 10^6$）的排列 $a$，再给 $q$（$\le 20$）个 $k$（$\le 10^6$）。对于每个 $k$，求出 $a$ 的一个最长不下降子序列 $b$，使得 $\sum{\ln(b_i-b_{i-1}+k)}$ 最大。对每组询问都输出一个答案。

首先显然有一种 $nq \log^2{n}$ 的 cdq 做法。但是题目...

题意： 给定一个图，点有权值。有两种操作： 1. 询问从点 $u$ 出发能到达的点中，权值最大的点（并把该权值变为 0）。 2. 删掉图中的某条边。

喵喵题

倒着来做，变成加边和改点权。建立 kruskal 重构树，边权按照查询的顺序。那么每次询问相当于询问一个子树！因为一个加边相当于连接两棵树。

似乎这种连通块相关的，有...

已完成 $SA$ 大学习。

$SA$，顾名思义，$Suffix \ Array$，就是后缀数组的意思。

我们先来考虑一个问题。给定一个字符串，多次询问，要我们求出两个后缀的 $\operatorname{lcp}$（最长公共前缀）。

先将字符串的每一个后缀全部插入一颗 $\operatorname{Trie}$ 树。可以发现询问就等价于询...

题意： 给定字符串 $s$。总共 m 个询问，每次给定 $a, b, c, d$，问你子串 $s[a..b]$ 的所有子串和 $s[c..d]$ 的最长公共前缀的长度的最大值是多少。 $1\le n,m\le 100,000$，$a\le b$，$c\le d$，$1\le a,b,c,d\le n$。

很有意思的一道题。 首先，看到字符串的题就可以先盲猜二分。显然这道...

题意：找有向图上平均值最大的环。 首先，看到平均值，可以想到分数规划。所以二分，判断是否有负环即可。 使用 dfs 判断，复杂度 $O(nm \log V)$

一道很有意思的题。

先让我们来观察一下。题目说的这个树是一个二叉树，所以每个点的度数小于等于三。

然后，题目要求我们找到一个树里面的点。并且只有 $\log n$ 次询问机会。$\log n$，定位某个点。好像在哪里见过？这很像 P4886。那道题我...

A： 显然两个数最后都要变成它们的 lcm。

B： 前 m - n 秒显然没用，最后 n 秒贪心抢蛋糕即可。

C： 注意到操作一相当于 $x \to \frac{x}{2}$，操作二相当于 $x \to 2^k + \frac{x}{2}$。所以直接二进制分解一下就行。

D： 如果 $\exists i, b_i > b_{i +...

1. 树分治

树分治是一种统计树上路径的方法。

例题：P2634 这道题要求我们统计树上长度为 3 的倍数的路径的个数。设 $(u,v)$ 表示 $u$ 到 $v$ 的路径。让我们先来考虑怎么统计满足 $lca(u,v) =...