题意

给了 $n$ 个串，要求从任意两个串中拿出一对前缀拼在一起的不同串数，可以同时选一个。

其中 $1 \le n \le 10^4$，串长至多为 $30$。

分析

感觉上是 Trie 树上结点数的平方，实际上有一堆重复。

重复的本质是一个 Trie 树结点的祖先，祖先到当前结点的路径是整个 Tire 树的某一个前缀。

构建出 $fail$ 树，$dfs$ 找到子树大小。

去重时，枚举每个结点，使用 $fail$ 指针向上跳到那个最远祖先，这个祖先内的所有串不包括自身，均重复了一次。

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

namespace ACAM {
    static const int maxp = 100000 + 5;
    int sz, ch[maxp][26], fail[maxp];
    int match[maxp], val[maxp];
    int node() {
        ms(ch[++sz], 0); fail[sz] = 0; val[sz] = 0;
        return sz;
    }
    void clear() {
        sz = 0; node();
        for (int i = 0; i < 26; i++) ch[0][i] = 1;
    }
    void insert(char* s, int i) {
        int u = 1;
        for (int i = 0; s[i]; i++) {
            int v = s[i] - 'a';
            if (!ch[u][v]) ch[u][v] = node();
            u = ch[u][v];
        }
        val[u]++; match[i] = u;
    }
    void build() {
        queue<int> q; q.push(1);
        while (!q.empty()) {
            int t = q.front(); q.pop();
            for (int i = 0; i < 26; i++) {
                if (ch[t][i]) {
                    fail[ch[t][i]] = ch[fail[t]][i];
                    q.push(ch[t][i]);
                } else {
                    ch[t][i] = ch[fail[t]][i];
                }
            }
        }
    }
}

动态最大独立集

显然有 $dp(u,0/1)$ 表示点 $u$ 是否选，转移显然。

把答案拆成两部分，只选取轻儿子的 $dp$ 值 $g(u,0/1)$ 和本来的 $dp$ 值 $f(u,0/1)$。

对于点 $u$ 的重儿子 $v$，可以列出转移方程：

$$
f(u,0)=g(u,0)+max(f(v,0),f(v,1))=max(g(u, 0)+f(v, 0), g(u,0) + f(v, 1)) \
f(u,1)=g(u,1)+f(v,0)
$$

定义一个广义的矩阵乘法，加法改为取 $\max$，乘法改为加法，则有转移矩阵：
$$
\begin{bmatrix}
g(u,0) & g(u, 0) \
g(u,1) & -\infty
\end{bmatrix}
\begin{bmatrix}
f(v,0) \
f(v,1)
\end{bmatrix}
=
\begin{bmatrix}
f(u,0) \
f(u,1)
\end{bmatrix}
$$
这个 $dp$ 现在可以改成用树链剖分维护每个点只选取轻儿子 $dp$ 值的矩阵。

一个点的 $dp$ 值，可以通过从该点重链的叶子结点往上转移的方式得到。

对于修改操作，一个点所处的重链均不需要修改，只需要修改重链的链头的父亲，记录一下修改前后的链头变化，更新一下这个父亲的矩阵，再通过重链往上爬。

单次操作复杂度：$\mathcal{O}(8\log^2n)$。

参考博客 树状数组黑科技讲义。

区间加 区间询问

令 $b_i=a_i-a_{i-1}$，那么 $a_x=\sum_{i=1}^x b_i$。于是，对于区间询问有

$$
\sum_{i=l}^r a_i = (r-l+1)\sum_{i=1}^{l-1} b_i + (r+1) \sum_{i=l}^r b_i - \sum_{i=l}^r i \cdot b_i
$$

分别在树状数组数组上维护 $b_i$ 和 $i \cdot b_i$ 即可。

权值树状数组二分第 $k$ 大

树状数组对应一棵没有右儿子的权值线段树，权值线段树上二分时，只需要和左儿子比较，因此权值线段树上二分可以扩展到树状数组上。

更新时，正常单点更新即可；二分时，每个点的权值对应线段树上结点的权值。

树状数组上结点 $p$ 的左儿子为 $p - lowbit(p) / 2$，右儿子为 $p + lowbit(p) / 2$。

注意边界上的细节，数组大小建议放大到 $2$ 的幂次。

题面

有 $m$ 个城市，每天选举办祭典次数最少且标号最小的的城市举办祭典，已知前 $n$ 天的举办情况，询问 $q$ 次第 $k$ 天的举办城市。

其中 $1 \le n, m, q \le 5\times 10^5, n+1 \le k \le 10^{18}$。

分析

处理出前 $n$ 天每个城市的举办情况，按照举办次数排序，将这个函数想象成水槽，发现之后的每天其实就是在这个类似阶梯的函数上注水。

如果知道当前位置的所处的注水高度和长度，将询问值减掉底下的面积并对长度取模，转化成询问这部分标号的第 $k$ 大。

因此，我们离线询问，维护当前水槽底部的面积和下一个台阶的整体面积。

题面

给定一个长度为 $n$ 的序列 $a$，等概率选择一个他的最长上升子序列，求每个位置被选到的概率。

其中 $1 \le n \le 10^5$。

分析

考虑如何求最长上升子序列的个数，令 $dp(i)$ 表示最长上升子序列最后一个数为 $i$ 时的长度和方案数二元组。

两个二元组合并时，若长度相同，则方案数相加，否则选一个长度大的。

对于位置 $a_i$，在询问小于 $a_i$ 的 $dp$ 信息和，将这个信息和的长度加一后，更新 $a_i$ 开始的后缀中每一个位置的信息。

树状数组加速即可。

回到原题。

我们对于每个前缀求出最长上升子序列的信息，和对应每个后缀的最长上升子序列信息。

每一个位置的概率的分母为总方案数，若其前缀和后缀的 LIS 长度相加再加一等于总体的 LIS 长度，那么选择它的方案数就是两个部分方案数的乘积，否则方案数为 0。

A Nauuo and Votes

B Nauuo and Chess

有 $n$ 个棋子，你要找一个最小的 $m \times m$ 的棋盘，放下这些棋子，要求两两曼哈顿距离大于下标之差的绝对值。

容易构造出沿着棋盘的上边和右边边缘放旗子即可。

C Nauuo and Cards

有 $n$ 张牌，编号为 $1$ 到 $n$，还有 $n$ 张空牌，现在你手上有 $n$ 张牌，桌上有 $n$ 张牌，你可以从桌上牌堆顶部摸一张，在放回一张到牌堆底部。

问最小操作次数，使得桌上按顺序为 $1,2,\dots,n$。

假如 $1$ 在手上，需要枚举出首先放几张空牌到桌上即可，其他情况类似讨论即可。

D Nauuo and Circle

给定一棵无根树，每个点编号为 $1$ 到 $n$，你现在需要将这棵树画在一个环上，满足环内不能有交叉。

固定根节点为 $1$，注意到一棵子树必须占据一段连续区间，一个点的儿子可以任意排列，每个儿子可以选择其度数个位置，容易 Tree DP。

E Nauuo and Pictures

给定 $n$ 个物品，每个物品有一个权值和是否被喜欢，做 $m$ 次操作，随机选择一个物品，其被选择的概率是其权值比上权值和，如果这个物品被喜欢则其权值加一，反之减一，求最后每个物品的权值期望。

注意到一个事实，每个物品的权值期望是正比于其权值的，因此只需要考虑权值为 $1$ 的情况即可。

相关证明 Codeforces Round #564 中文题解。

也可以理解，把一个物品拆成了 $w$ 个。因此可以看成两个巨大物品，喜欢和不喜欢两种总和。

对 $m$ 次操作做 $\mathcal{O}(m^2)$ 的 $dp$。

记 $f(i,j)$ 表示前 $i$ 次操作做了 $j$ 次加操作，$f(i,j)$ 可以转移到 $f(i+1,j+1)$ （选择一个喜欢的物品）或者 $f(i+1,j)$ （选择一个不喜欢的物品），除上概率。

最后，对于每个物品，根据其是否喜欢，在两种中权值的比重乘上前面计算的系数即可。

性质一

所有长链的长度和是 $\mathcal{O}(n)$ 的。

性质二

一个点的 $k$ 级祖先所在重链长度至少为 $k$。

$\mathcal{O}(n\log{}n)$ - $\mathcal{O}(1)$ 在线询问 $k$ 级祖先

首先预处理出倍增数组，再预处理每个数的最高位在哪，再预处理每条重链的端点长度为 $l$，顶点往上走 $l$ 步和沿着重链走 $l$ 步是哪些点。

对于 $k$ 级祖先，令 $r=highbit(k)$，显然 $r>k-r$，用倍增数组将询问点向上跳 $r$ 步到 $y$ 点。

由性质二，$y$ 所在链长大于等于 $r > k - r$。

最坏情况下，$y$ 就是一个重链顶点，由于其预处理了往上走至少 $r$ 步的点，因此可以直接回答，否则重链顶点在 $y$ 到答案的路径上，显然也可以直接回答。

第二种情况，$y$ 的重链端点是答案的祖先，那么显然 $y$ 和答案在一条重链内，也可以直接回答。

$\mathcal{O}(n)$ 统计每个点子树中以深度为下标的可合并信息

重儿子继承父亲的信息，由于信息是以深度为下标，因此只需数组指针移位。

轻儿子暴力将信息与父亲合并。

复杂度是 $\mathcal{O}(\sum\text{重链长度})$，即 $\mathcal{O}(n)$。