CF1677E
本题转化之后就是矩阵覆盖，矩阵查询被覆盖的点数。现在将讲解线段树如何实现这个。
扫描线的话将转化为求区间为 \(0\) 个数的历史和，历史和是很难的。
注意到我们每次把当前序列加入历史和去也就是把区间为 \(0\) 的位置加 \(1\)。
所以我的想法是在线段树节点上加一个标记 tms 表示当前区间还需要被累加进历史和多少次。
我们总共有两个标记，tag 是表区间加，tms 表区间累加，我们不妨先 tag 后 tms。
注意到如果当前有 tms，有 tag 来之后，需要 pushdown.
然而这真的是太蠢了，我们观察性质，注意到如果矩阵有交那么他们一定有同一个 \(\max\)。
所以我们对于每个 \(\max\)，做好容斥即可。不妨树状数组解决。
具体地，我们还是要维护历史和，但是我们可以差分，在第 \(i\) 个版本插入时贡献乘上 \(n-i\)。
AGC016E
我们想到可以从底往上推。初始有一个 \(O(n^2m)\) 的做法，我们枚举答案，然后自底往上推。
维护一个集合 \(S\) 表示当前必须存在的元素。那么如果当前遇到 \((i,j),i,j\in S\)，那么就非法。
否则，对于 \((i,j)\) 存在一个数 \(\in S\) 的，那么把另一个数加入 \(S\)。
不妨只枚举 \(x\) 只让 \(x\) 从底往上推，那么 \(x,y\) 合法的话，首先要他们分别合法。
其次，对于每个时刻，\((i,j)\) 不能在两个集合里分别存在。直接模拟该过程判断还是 \(O(n^2m)\)。
我们想，若 \((i,j)\) 分别位于两个集合了，那么最后的 \(i,j\in S_x,S_y\)，所以只需要判断 \(S_x\cap S_y\) 非空。
AGC044C
我们猜是字典树。但是我们建的不是常规的 01-trie，而是三进制字典树。
12 交换的操作我们很容易实现，直接打 tag 即可，代表当前节点需要交换 12。
然而全局 \(+1\) 的操作呢？如果我们按照普通的从高位建到低位，发现是很难实现。
所以这启发我们从低到高建字典树，每次我们就轮换 012。
发现 12 儿子是没有变化的，我们递归 0 儿子，发现这个 0 儿子进位 \(1\) 也是要实现轮换 012。
所以直接沿着 0 这条链递归下去即可。
CF643E
惨遭诈骗。由于最后答案是输出浮点数，而浮点数精度有限，所以我们不妨少维护一点。
我们拆贡献的时候，深度 \(\ge 50\) 的概率我们直接忽略，因为这里的值太小了。
所以我们记 \(f_{u,d}\) 表示 \(u\) 子树内深度为 \(j\) 的概率。那么考虑容斥，\(1-f_{u,d}=\prod (1-\frac{1}{2}f_{v,d-1})\)。
当我们新加入一个点的时候，向上更新 \(50\) 个祖先即可。
CF48F
这个题非常抽象啊。先把 \(n\) 天独立开来。
发现如果我们把 \(m\) 种商品都拿出来排序后贪心就行了，但是排序需要 \(\log n\) 是不行的。
考虑二分，每次找第 \(mid\) 大的数出来，看看 \(\le mid\) 的是否超过 \(w\)，按这个二分下去。
利用 nth_element 是线性的，而且我们每次规模是减半的，所以 \(T(n)=T(\dfrac{n}{2})+n\)。
那么复杂度 \(O(nm)\)。为了精度可以整数与小数分开。
AGC026D
观察到已知一行，再填下一行有只有不超过两种填法，当且仅当上一行红蓝交错时有两种。
于是我们在笛卡尔树上 dp，存两个状态，代表交错的方案数和不交错的方案数。
P10013 [集训队互测 2023] Tree Topological Order Counting
我们显然要求的是所有 \(u,k\)，点 \(u\) 在拓扑序上排第 \(k\) 的方案数。
我们可以对于每个 \(u\) 往上跑一遍直到根，顺便维护 \(f_k\) 表示当前子树内，\(u\) 排第 \(k\) 的方案数。
做类似背包的合并。设从 \(v\) 转移到 \(fa_v=u\)，排名 \(k_1\) 转移到排名 \(k_2\)，
若 \(u\) 除去 \(v\) 子树后拓扑序的个数为 \(g\)，那么系数是 \(C_{k_2-1}^{k_1-1}\times C_{siz_u-1-k_2}^{siz_v-k_1}\times g\)。
最后因为 \(u\) 要排在前面，所以 \(k_2\) 要加上 \(1\)。
一个 \(u\) 复杂度是 \(O(n^2)\)，总的复杂度是 \(O(n^3)\)。
注意到对于 \(x\to fa_x\) 这种转移系数都是一样的，对于 \(x\) 子树内的 \(u\) 都可以转移。
所以我们可以从根开始往下做。考虑同时对所有 \(u\) 转移。
可以将状态的转移看做有向图，转移系数看做边，我们所求的是所有路径的积的和。
对于 \(dp_{1,k}\)，我们将其在连一条边到源点，边权为 \(b_i\) 即可。
交换起点和终点，我们原来求的是 \(dp_{u,1}\to dp_{1,k}\) 的所有路径，我们不妨求所有 \(dp_{1,k}\) 到 \(dp_{u,1}\) 的路径。
那么我们把这个有向图反过来就行了。对于 \(u\) 点的答案即为 \(f_{u,1}\times g_u\)。
P10008 [集训队互测 2022] Range Minimum Element
考虑建立 \(a\to b\) 的双射关系，题目中已经有 \(a\) 生成 \(b\) 的方式，现在考虑从 \(b\) 生成 \(a\)。
我们现在已知 \(b\)，\(b\) 从大到小，设当前权值为 \(x\)，每次把对应的 \(a\) 区间里的没有被填的数全部设为 \(x\)。
如果不存在还没有被填的数并且没有 \(x\)，那么 \(b\) 就是不合法的，但是我们可以继续构造出 \(a\)。
如果最后还有未填的数设为 \(1\)。
那么，每个合法的 \(b\)，都有唯一的 \(a\) 与其对应。
如果是不合法的 \(b\)，也有 \(a\) 与其对应，并且，这个 \(a\) 是可以由一个合法的 \(b\) 生成而来。
只需要把不合法的那个 \(x\) 换成上一个 \(x\) 即可。
那么现在我们计数 \(a\)，使得 \(a\) 是可以被 \(b\) 构造出来的。
考虑区间 dp，每次找最左的 \(a_i=1\) 出来，那么 \([1,i-1]\) 的区间已经被填满，即并集为 \([1,i-1]\)。
而且越过 \(i\) 的区间，满足 \(x=1\)，我们之后可以不管了。
在 \([1,i-1]\) 这个区间，最小值一定 \(\ge 2\)。在 \([i+1,n]\) 这个区间，我们重复找最左的 \(a_i=1\)。
如果找不到 \(a_i=1\) 呢？那么我们可以找 \(a_i=2\)，继续找罢了。
具体地，设 \(dp_{l,r,p}\) 表示区间 \([l,r]\)，满足最小值 \(\ge p\) 的方案数。同时设 \(I_{l,r}\) 表示 \([l,r]\) 并集是否填满。
那么 \(dp_{l,r,p}=I_{l,r}\times dp_{l,r,p+1}+\sum_{i\in[l,r]} dp_{l,i-1,p+1}\times dp_{i+1,r,p}\times I_{l,i-1}\)。
但是 \(c\) 有点大，由于 dp 的转移过程是简单加乘，所以最后的答案是一个 \(n\) 次多项式，不妨插值。
复杂度 \(O(n^4)\)。
P3270 [JLOI2016] 成绩比较
考虑二项式反演，先钦定 \(j\) 个人被碾压。其贡献是 \(C_{n-1}^j\)。
每门课是独立的，考虑某门课，枚举 B 神的分数 \(x\)，贡献是 \(\sum_{x=1}^Ux^{n-R}\times (U-x)^{R-1}\times C_{n-j-1}^{R-1}\)。
只需要把每门课的贡献乘起来即可。
然而课程的贡献计算复杂度基于值域，而这是个 \(n\) 次多项式，不妨插值。
P2048 [NOI2010] 超级钢琴
这是典题。堆里维护每个右端点，左端点还剩哪些区间可以取，每次取出 rmq，然后分割区间。
因为 \(k\) 很小，所以取 \(k\) 次即可。