前置知识：\(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)\)，复杂度瓶颈在排序