CF2178G
圆环上有 2n2n 个等间距的点,按顺时针顺序标记为 1, 2, \dots, 2n1,2,…,2n。有 nn 条具有不同端点的弦,其中第 ii 条弦连接 a_i, b_iai,bi。现在按照顺序依次连接这 nn 条弦。
每当连接完前 \ellℓ 条弦以后,考虑这 \ellℓ 条弦的任意非空子集 SS。设 SS 中元素的索引分别为 c_1, c_2, \dots, c_mc1,c2,…,cm,若对于所有的 1 \leq i < m1≤i<m,都满足弦 c_ici 与弦 c_{i + 1}ci+1 相交,则称 SS 为一条链。
当且仅当,每一条弦在前 \ellℓ 条弦的所有子集链中出现偶数次时,称这些弦是紧密连接的。
对于 11 到 nn 的每一个 \ellℓ,你都需要判断前 \ellℓ 条弦是否紧密连接。
数据范围:2 \leq n \leq 5 \times 10^52≤n≤5×105,1 \leq a_i < b_i \leq 2n1≤ai<bi≤2n。
时空限制:33s / 512512MiB。