动态最大独立集

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

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

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

定义一个广义的矩阵乘法，加法改为取 $\max$，乘法改为加法，则有转移矩阵：

这个 $dp$ 现在可以改成用树链剖分维护每个点只选取轻儿子 $dp$ 值的矩阵。

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

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

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

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

区间加 区间询问

令 $b_i=a_i-a_{i-1}$，那么 $a_x=\sum_{i=1}^x 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)$。

A From Hero to Zero

B Catch Overflow!

C Electrification

给定 $x$ 正半轴的 $n$ 个点，求一个点 $x$ 到所有点距离的第 $k+1$ 大的最小值。

二分答案，当前值为 $m$，考虑线段 $[a_i-m,a_i+m]$，就是判是否有一个点被覆盖了 $k+1$ 次。

判断过程可以双指针扫一下，具体参考代码。

D Array Splitting

给定一个序列 $a$，将一个区间分成 $k$ 个连续段，记 $f(i)$ 表示 $i$ 属于第几个段，最大化 $\sum_{i=1}^n a_if(i)$。

考虑贡献，首先每个位置都加了一次，某些后缀多加一些次。

其实就是对所有后缀排序，取前 $k$ 大，注意整体是必选的即可。

E Minimal Segment Cover

给定 $n$ 条线段，询问 $q$ 次一个线段内所有点是否被覆盖，包含非整数点。

因为要包含整数之间的部分，因此考虑一个贪心的跳转的过程，每个点跳一次到最右端点，然后从这个位置继续往后跳。

这个跳转过程可以用倍增进行加速，预处理每个位置被一条线段覆盖到的最右端点，倍增一下。

F The Number of Subpermutations

给定序列 $a_1, a_2, \dots, a_n$，求有多少个子区间是对应长度的排列。

观察一下，要么 $1$ 很少，要么重复的数字很多。枚举包含 $1$ 的子区间，向右跑到出现相同数字停止，判断这个点为右端点的子区间是否是一个排列，即判断两个集合是否相同。随机一个权值异或判断即可。

模板

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

const int mod = 998244353;
const int inf = 1 << 30;
const int maxn = 1 << 18;

int n, a[maxn], b[maxn], c[maxn], d[maxn], e[maxn], f[maxn];

void fwtOR(int a[], int n, int op = 1) {
    for (int d = 1; d < n; d <<= 1)
        for (int i = 0, t = d << 1; i < n; i += t)
            for (int j = 0; j < d; j++) {
                if (op == 1)
                    a[i + j + d] = (a[i + j + d] + a[i + j]) % mod;
                else
                    a[i + j + d] = (a[i + j + d] + mod - a[i + j]) % mod;
            }
}
void fwtAND(int a[], int n, int op = 1) {
    for (int d = 1; d < n; d <<= 1)
        for (int i = 0, t = d << 1; i < n; i += t)
            for (int j = 0; j < d; j++) {
                if (op == 1)
                    a[i + j] = (a[i + j] + a[i + j + d]) % mod;
                else
                    a[i + j] = (a[i + j] + mod - a[i + j + d]) % mod;
            }
}
void fwtXOR(int a[], int n, int op = 1) {
    for (int d = 1; d < n; d <<= 1)
        for (int i = 0, t = d << 1; i < n; i += t)
            for (int j = 0; j < d; j++) {
                int x = a[i + j], y = a[i + j + d];
                a[i + j] = (x + y) % mod;
                a[i + j + d] = (x + mod - y) % mod;
                if (op != 1) {
                    // inv2 = 499122177
                    a[i + j] = 1ll * a[i + j] * 499122177 % mod;
                    a[i + j + d] = 1ll * a[i + j + d] * 499122177 % mod;
                }
            }
}

int main() {
    scanf("%d", &n);
    int m = 1 << n;
    for (int i = 0; i < m; i++) scanf("%d", a + i), c[i] = a[i], e[i] = a[i];
    for (int i = 0; i < m; i++) scanf("%d", b + i), d[i] = b[i], f[i] = b[i];
    fwtOR(a, 1 << n); fwtOR(b, 1 << n);
    for (int i = 0; i < m; i++) a[i] = 1ll * a[i] * b[i] % mod;
    fwtOR(a, 1 << n, -1);
    for (int i = 0; i < m; i++) printf("%d%c", a[i], " \n"[i == m - 1]);
    fwtAND(c, 1 << n); fwtAND(d, 1 << n);
    for (int i = 0; i < m; i++) c[i] = 1ll * c[i] * d[i] % mod;
    fwtAND(c, 1 << n, -1);
    for (int i = 0; i < m; i++) printf("%d%c", c[i], " \n"[i == m - 1]);
    fwtXOR(e, 1 << n); fwtXOR(f, 1 << n);
    for (int i = 0; i < m; i++) e[i] = 1ll * e[i] * f[i] % mod;
    fwtXOR(e, 1 << n, -1);
    for (int i = 0; i < m; i++) printf("%d%c", e[i], " \n"[i == m - 1]);
    return 0;
}