AGC061C
答案为什么不是 \(2^n\)，因为有可能选择不同的左右端点可能会导出相同的排列。
考虑把一种选择刻画为 \(01\) 序列 \(a_i\)，\(a_i=0\) 表示选择左端点，\(a_i=1\) 表示选择右端点。
那么对于两个不同的序列 \(a,b\)，如果导出的排列相同。
找到第一个 \(a_i\ne b_i\) 的位置，假设 \(a_i=0,b_i=1\)。
那么与 \(i\) 相交的线段，在左侧必须选 \(0\)，在右侧必须选 \(1\)，与 \(i\) 相交的构成连续区间。
对于所有 \(a_i\ne b_i\) 的位置，影响的区间是不相交的。
然后可以考虑容斥。
\(dp_i\) 表示考虑了前 \(i\) 条线段的答案。
考虑转移
\[dp_{i-1}\times2\rightarrow dp_i\\ -dp_{l-1}\rightarrow dp_r \]\([l,r]\) 是所有的影响区间。
时间复杂度：\(O(n)\)。
标签：ne,相交,AGC061C,端点,dp,rightarrow From： https://www.cnblogs.com/hellojim/p/17129736.html