260127 模拟赛
T1
有一个长度为 \(n\) 的序列 \(a\) 和 \(m\) 个操作，每个操作如下：
1 x：\(a_x\gets 0\)；2 v：\(\forall i\in [1,n],~a_i\gets \max(a_i,v)\)；
有 \(q\) 次删除操作，每次删除操作序列中的一个操作，你需要回答：经过操作序列中的操作之后，\(\sum a_i\) 是多少。每次操作对 \(a\) 数组的改变不会影响下一次操作。
\(n,m\le 3\times 10^5,~v,a_i\le 10^9\)
注意到对每个下标我们只关心最后一次 1 操作以及后面 \(v\) 最大的 \(2\) 操作。如果没有 1 操作，我们可以用 BIT 维护 \(a\)，用可删堆维护全局 \(v\) 的最大值。对于剩下的下标，我们用线段树维护时间轴，把序列上的下标放在最后一次 1 操作对应的下标上，然后用线段树上二分维护 \(v\) 的向左上升链，于是做完了。
T2
给定两棵包含 \(n\) 个节点的树 \(T_1,T_2\)。对于一个点集 \(S\) 记 \(f_{1/2}(S)\) 表示在 \(T_{1/2}\) 上 \(S\) 的最小斯坦纳树上编号最大的节点。请你求出有多少个非空集合 \(S\) 满足 \(f_1(S)=f_2(S)\)。
\(n\le 2\times 10^5\)
首先枚举 \(f(S)\) 的值 \(x\)，那么最小斯坦纳树不能跨过 \(>x\) 的节点，于是考虑 kruskal 重构树，从小到大加点，每次合并若干连通块。考虑计算贡献，如果 \(S\) 包含 \(x\)，那么剩下的部分可以随便选，方案数等于 \(2\) 的(两连通块的交集大小)次方。如果 \(S\) 不包含 \(x\)，那么要求 \(S\) 在两棵树中都至少出现在两棵子树内。这个过程可以通过容斥转化成 \(4\) 个子问题：
- \(S\) 在 \(T_1\) 中必须分布在同一棵子树内；
- \(S\) 在 \(T_2\) 中必须分布在同一棵子树内；
- \(S\) 在 \(T_1\) 和 \(T_2\) 中都分布在同一棵子树内；
- 没有限制；
这个过程考虑启发式合并，对于轻子树可以直接 \(O(sz)\) 暴力扫一遍，用并查集和桶数组简单统计；对于重子树可以把对面的所有子树都 \(O(cnt)\) 扫一遍，注意到我们可以 \(O(1)\) 求两棵数两个连通块的交集大小。具体的，由于每个节点只会贡献一个连通块二元组，因此非零的连通块二元组肯定不超过 \(n\) 个，可以直接用哈希表维护。于是就都做完了，时间复杂度显然 \(O(n\log n)\)。
写 umap 被卡常了，换成了手写哈希表和数组直接通过，赛时-35pts。
T3
有 \(n+\sum a_i\) 张卡牌，每张上都写着一个数字，其中有 \(n\) 张卡牌依次写着 \(a_{1\sim n}\)，其余 \(\sum a_i\) 张都写着 \(-1\)。
有一个变量初始为 \(0\)，每次你可以取出一张卡牌，将它加上卡牌上的数字，每张卡牌只能取一次。如果某次操作结束后变量的值变成了 \(0\)，那么你得一分。请你对于 \(k\in [1,n]\) 求出你得 \(k\) 分的出牌方案数。两种方案不同当且仅当某一时刻你出了两张数字不同的卡牌。
\(n,a_i\le 5000\)
注意到每次变成 \(0\) 的时刻可以将操作序列划分为若干子段，每段内恰好有 \(1\) 次变成 \(0\)（结尾）。考虑对段进行容斥，钦定一些时刻前缀和为 \(0\)，求出方案数后可以直接反演。
考虑一段的总方案数，为可重集排列的方案数 \(\prod_{i=1}^{k}{\Bigl(\sum_{j\in S} a_j+i\Big)}\)，其中 \(S\) 为段中 \(a_i\) 构成的可重集。这个东西不很好看，考虑神秘组合意义，段内一个点 \(i\) 向另一个点 \(j\) 可以连接一条权值为 \(a_j+[j\le i]\) 的边，这样答案就是随意连边，权值积的和。
注意到连出来是一个内向基环树森林，但因为有集合 \(S\) 内部连边的限制所以还是做不了。考虑先求出划分为恰好 \(k\) 个连通块的方案数，然后用第二类斯特林数将它进一步划分为若干集合。这样我们就只对连通块的数量而不是所在集合有要求了。
恰好 \(k\) 个连通块就是恰好 \(k\) 个环，不在环内的点可以任意连边（权值为 \(\sum_{j=1}^{n}a_j+i\)），再使用二项式反演转化成钦定 \(k\) 个环的方案数。考虑一个环的权值是什么，为了简化自环的贡献，我们将 \(a_j+[j\le i]\) 改写成 \((a_j+1)-[j>i]\)，这样可以看成是任意选择环上一些单调增加的边，将其权值改为 \(-1\)，因此可以看成是将环划分为若干单增的链，链内部的贡献为 \(-1\)，链尾的贡献为 \(a_i+1\)。然后我们用第一类斯特林数将若干条链拼成若干的环，就是基环树划分的答案。链划分显然可以 dp。
时间复杂度 \(O(n^2)\)。