【CF429E】 Points and Segments（欧拉回路）

2023-01-12 07:30:44

传送门

考虑欧拉回路有一个性质。
如果把点抽出来搞成一条直线，路径看成区间覆盖，那么一个点从左往右被覆盖的次数等于从右往左被覆盖的次数。

发现这个性质和本问题十分的相似，那么我们就想一下怎么欧拉回路解决。
考虑显然可以差分对吧，如果把红色的贡献看成\(+1\)，蓝色的看成\(-1\)，那么就可以差分了。

那么这个也等价于欧拉回路，接着考虑对于奇数点，两两之间匹配就好了。