1.AGC061C
link && submission
很神仙的一道题。先考虑所有的人都选择 \(a_i\) 时刻登记。那么对于一个人来说他变成 \(b_i\) 的时会增加贡献当且仅当 \([a_i,b_i]\) 之间有其他人被登记。
定义 \(C\) 数组, \(C_i\) 为 0 表示第 \(i\) 个人在 \(a_i\) 被登记，为 \(1\) 表示第 \(i\) 个人在 \(b_i\) 被登记。考虑将计数转换成对 \(C\) 计数，但是由上所述，有时候 C 数组不同所得到的序列却是相同的。于是考虑定义合法，将序列对应的最终顺序唯一化。合法不好算，转换成全部的减去不合法的。
定义不合法为存在一个 \(i\) 满足 \(C_i=1\) 但 \(C_i\) 变为 \(0\) 后最终顺序不改变。
还是由上所述，对于 i 来说他不合法说明 \([a_i,b_i]\) 没有其他人被登记了，也就是说对于任意的 j 来说，如果 \(a_j\in [a_i,b_i]\) 那么 j 就只能在 \(b_j\) 被登记才有可能让 i 不合法。\(b_j\in [a_i,b_i]\) 也是同理。
处理出每个位置 $ i $ 的 $ l_i $ 和 $ r_i $，其中 $ l_i $ 表示最小的满足 $ b_j > a_i $ 的 $ j $ ，$ r_i $ 表示最大的 $ j $ 满足 $ a_j < b_i $ 的 $ j $。所以当 $ i $ 不合法时有 $ C_{l_i} = C_{l_i + 1} = \cdots = C_{i - 1} = 0 $ ，$ C_{i} = C_{i + 1} = \cdots = C_{r_i} = 1 $，此时 $ l_i \sim r_i $ 的值是确定的。
显然 \(l,r\) 是单调的，然后如果对于 i,j 有 $[l_i,r_i] $ 和 \([l_j,r_j]\) 是相交的，那么两个位置一定不能同时不合法。
所以问题就转换成了选择 \(k\) 个区间，\(k\in [0,n]\)，区间内不不相交，每个选择方案的容斥贡献是 \(2^x(-1)^y\)，\(x\) 为未被覆盖的节点个，\(y\) 为区间选择个数。然后考虑刷表