题解：CF2170E Binary Strings and Blocks

· · 题解

题目传送门

容斥做法。

不合法显然是存在一个区间全都是 0 或 1，首先把包含了其它区间的区间扔掉，上个树状数组即可。

然后考虑容斥，定义 f_i 为以按左端点排序第 i 个区间为最后一个不合法区间的贡献，l_i 和 r_i 为第 i 个区间的左右端点。

得到以下转移式：

f_i =2^{n-r+l} - \sum_{j=1}^i f_j \times 2^{r_i-r_j} \times 2^{\max(0,l_i-r_j)}

答案为 2^n-\sum_{i=1}^n f_i。

发现 l_i-r_j \ge 0 的是一段前缀，且范围逐渐增大，可以拿一个指针分别维护取 0 和取 l_i-r_j 的贡献。

时间复杂度 O(n \log n)。

submission。