F. Intersection and Union
容易想到对区间的每个点计算其在多少种符号序列中,能够最终剩下来。
而且一个区间的所有点在整个坐标轴上的位置是连续的,因此通过差分,我们可以时刻维护出一个点在哪些区间中出现。
我们把包含这个点的区间称为关键点,不包含的称为非关键点。
问题就变成了如何快速对一个关键点集合求出有多少种方式能够使得最终集合包含当前点。
(因为没有关标签,看到了矩阵的标签,于是就很容易想到列出递推式,然后用线段树维护,如果没看到标签的话,可能会去想如何把贡献拆到每个关键点的坐标上?)