CF1830C

原题

翻译

前置知识：\(catalan\)数

首先我们先考虑如果没有线段怎么做

我们容易发现如果\(n\)为奇数肯定无解，如果\(n\)为偶数答案为第\(\frac{n}{2}\)个\(catalan\)数

然后我们考虑如果两个线段相交这里会产生什么影响，即对于线段\([l_1,r_1]\)和\([l_2,r_2]\)满足\(l_1 \leq l_2 \leq r_1 \leq r_2\)，我们容易发现其方案数等价与三个线段内的括号序列合法：

• \([l_1,l_2-1]\)

• \([l_2,r_1]\)

• \([r_1+1,r_2]\)

我们考虑如果两个线段重叠会产生什么影响，即对于线段即对于线段\([l_1,r_1]\)和\([l_2,r_2]\)满足\(l_1 \leq l_2 \leq r_2 \leq r_1\)，我们容易发现其方案数等价与两个线段内的括号序列合法：

• \([l_2,r_2]\)

• \([l_1,l_2-1] \cup [r_2 + 1, r_1]\)

于是我们可以得出结论：设\(S_i\)表示\(i\)位置被\(S_i\)集合内的线段覆盖。则所有\(S_i\)相同的位置可以单独计算贡献，所有方案相乘即为答案

于是我们考虑一些奇技淫巧随机化算法

我们为每一个线段赋一个随机权值\(b_i\)，让区间\([l,r]\)内所有位置异或上这个随机权值

则对于\(S_i,S_j\)值不同的两个位置\(i,j\)，将以高概率\(a_i,a_j\)不同；相反的，如果\(S_i,S_j\)值相同，高概率\(a_i,a_j\)也相同

因此我们只需要对\(a_i\)离散化后对每一个相同的\(a_i\)单独计算贡献，所有方案相乘即为答案

最终复杂度\(O(nlogn)\)，复杂度瓶颈在排序