闲话
APJifengc：
您都已经切 AGC 的 E 了 您太强了
您都已经写一个美元符号了 您太强了
不懂
发现 APJ 老师回家卷数奥的反常积分题
太强了
SoyTony：APJ 是美国间谍 —— 白宫咋不用支付宝？白宫还是太不懂了
how to solve
\[\int_0^{\pi / 2} \frac{x}{\tan x} \text d x \]？
\(\text{Simu}\)
T1
设一个点的标号是这个点作为被删除的子树的根对应的操作的编号。若一个点祖先中最小编号是 \(x\)，则它对 \([1, x - 1]\) 的答案都有贡献。
这个可以直接从小到大枚举每个点后用父亲更新得到，随后维护差分即可。
不用 dfs，常数小点。\(O(n)\)。
T2
对点 \(i\) 的答案就是每个点 \(u\) 以 \(i\) 为根的子树内权值小于 \(u\) 的权值的点数之和，考虑换根。
以 1 为根的答案是易算得的，用树状数组统计即可。同时维护一个这个子树内权值小于 \(fa[u]\) 的权值的点数。
然后考虑换根。当根从 \(u\to v\) 时，\(v\) 对答案的贡献变为 \(0\)，\(u\) 对答案的贡献为不在以 1 为根时 \(v\) 子树内的点的贡献。
拿总数直接减就行了。\(O(n\log n)\)。
T3
问题是经典的 dp，又带修，考虑上线段树维护。
若第 \(i\) 个字符是 ABC 中的第 \(0\le k\le 2\) 个，则第 \(i\) 个位置的矩阵就是第 \(k\) 行全 \(1\) 的单位矩阵。
证明？考虑写出转移即可。
然后修改也很简单了。\(O(4^3n\log n)\)。
T4
我怎么不会贪心？哦我一直不会啊那没事了。
原题是普及-，有个经典结论是答案就是 \(\sum \max(0, a_i - a_{i - 1})\)。
现在考虑配对。考虑一种贪心策略，遍历 \(b_i\)，若有 \(b_i > 0\) 将其压入队列中，\(b_i < 0\) 则：若使得代价最大，与最靠左的 \(b_i\) 配对；若使得代价最小，与最靠右的 \(b_i\) 配对。
注意到 \(a_i\ge 0\) ，所以我们一定能找到数字配对。可以用交换法证明贪心的正确性。
\(O(n)\)。
杂题
随机开 At 的题 开到了 AGC
很快啊 D 没看懂所以不写了
今天的 e 有 poly 做法
但我 f 也做了
我看我哪个先写（
给定两个长度为 \(n\) 的 01 串 \(A, B\)。保证两个串内的
1数量相同，设有 \(m\) 个。令 \(\langle a_i\rangle , \langle b_i\rangle\) 分别表示 \(A, B\) 中1的所有下标按顺序排列组成的序列。随机打乱 \(a, b\) 序列，按这序列的下标 \(i\) 从小到大顺序交换 \(A[a_i]\) 和 \(A[b_i]\)。令 \(p\) 表示操作完成后 \(A = B\) 的概率，请求出 \(p\times (k!)^2\) 在模 \(998244353\) 意义下的值。\(1\le n\le 10^4\)。
很好玩的题啊（
答案就是计数满足结果有 \(A=B\) 的操作序列数量。
可以发现，我们若想使得 \(A = B\)，则需要构造操作序列，让 \(A\) 中多的 \(1\) 被转移到 \(B\) 中是 \(1\) 而 \(A\) 中是 \(0\) 的位置。这种操作序列定形如 \(S\to U\to \cdots\to U\to T\)，其中 \(S, U, T\) 都指代一系列位置 \(k\) 中的一个，两个位置 \(k_1, k_2\) 写作 \(k_1 \to k_2\) 表示交换 \(A[k_1]\) 和 \(A[k_2]\)。
\(S = a \in \{k : A[k] = 1 \land B[k] = 0\}\)；
\(U = a \in \{k : A[k] = 1 \land B[k] = 1\}\)；
\(T = a \in \{k : A[k] = 0 \land B[k] = 1\}\)；
可以发现，如果构造一个节点数为 \(n\) 的图，将一个操作看做 \(a\to b\) 的连边，则我们需要的就是一系列以 \(S\) 类位置开始，\(T\) 类位置结束，中间经过一系列 \(U\) 类位置的链。
考虑 dp 这个图的形态。由于 \(S, T\) 两类位置是对称的，他们的总数相同，记作 \(p\)；\(U\) 类位置的总数记作 \(q\)。由于并不需要用到所有 \(U\) 类位置，我们可以在 dp 数组中加一维表示使用的 \(U\) 类位置数。
我们设 \(f(i, j)\) 为有 \(i\) 条链，包含 \(j\) 个 \(U\) 类位置的图。则我们有两种转移：
- 可以加入一个 \(S\) 类位置和一个 \(T\) 类位置组成新的一条链，钦定放在末尾。这时我们从 \(i\) 个已有的 \(S\) 类位置中选一个，\(T\) 类位置同理，共 \(i^2\) 种选法。
\(f(i - 1, j) \times i^2 \to f(i, j)\) - 可以加入一个 \(U\) 类位置进一条链，钦定放在末尾。链彼此不同，位置彼此不同，共 \(i\times j\) 种选法。
\(f(i, j - 1) \times ij \to f(i, j)\)
初值有 \(f(0, 0) = 1\)。
答案的统计需要枚举用了多少个 \(U\) 类位置。假设有 \(k\) 个位置没有在链内，则 \(\dbinom{p}{k} \times (k!)^2\) 就是他们内部形成的形态数；链间的配对方案数是 \(\dbinom{m}{k}\)。即
\[\sum_{k = 0}^q f(p, q - k)\times \dbinom{p}{k} \times (k!)^2\times \dbinom{m}{k} \]总时间复杂度 \(O(n^2)\)。
标签：le,闲话,位置,times,23.3,答案,序列,配对 From： https://www.cnblogs.com/joke3579/p/chitchat230302.html