Solved：5/8
Upsolved：6/8
Rank：166
E. MEXmize the Score
题意
定义一个集合的分数为：将它分成若干个子集，mex 和的最大值。（mex 从 0 开始算）
给 n 个数，求所有非空子集的分数之和。
\(n\leq 2\times 10^5\)
题解
对一个确定的集合，它的划分方式一定是每次分出去一个最长的 {0,1,…,k}，按这样划完剩下的数就没用了。
我们依次考虑 {0}，{0,1}，…，{0,1,…,n-1} 被划分了多少次。
对 {0,1,…,i}，如果某个子集满足：i+1 及以上的数字随意，如果 0 到 k 出现了至少 j 次且至少一个数出现了 j 次，那么 {0,1,…,i} 在这个子集中被划分了 j 次。
这里的 {0,1,…,i} 是从 {0,1,…,i-1} “延申”出来的。因此对答案的贡献是 1 而不是 i+1（如果不用差分统计贡献，需要保证 i+1 不出现或者出现次数和 1…i 的次数恰好差 j，需要多枚举一层）。
具体式子就是
\[\sum_{i=0}^{n-1}2^{\sum_{j=i+1}^nc_j}\sum_{j=1}^{c_i}j\left(\prod_{k=0}^i\sum_{l=j}^{c_k}\binom{c_k}l-\prod_{k=0}^i\sum_{l=j+1}^{c_k}\binom{c_k}l\right) \]k 和 l 的循环可以预处理，只需枚举 i 和 j。复杂度 O(n)。
F. Orangutan Approved Subarrays
题意
称一个序列是可消除的，如果它可以通过如下操作删除至空序列：
- 每次删除一个连续的数字相等的区间
- 每个数字只能删除一次
给一个序列，多次询问一个区间是否可消除。
\(n\leq 2\times 10^5\)
题解
首先观察到两个性质：
- 序列可消除的充要条件是不存在交替出现的数字（1 2 1 2 这样的，中间隔其他数也不行）
- 如果一个区间不是可消除的，那么包含它的区间也不是可消除的。因此可以固定右端点然后双指针算最长的左端点。
考虑左端点何时会向右移动。维护last和next数组分别表示每个数字上次和下次出现的位置，则当右端点为i时，只要[j,last[i]-1]中存在一个数的next在[last[i],i-1]之间，就说明有交替出现。动态更新next并用线段树维护即可。
处理完所有右端点对应的左端点，询问O(1)。
标签：2024.10,last,数字,19,sum,next,端点,Div.2,消除 From： https://www.cnblogs.com/EssentialSingularity/p/18514580