@MLEAutoMaton
2019-03-29T14:30:49.000000Z
字数 231
阅读 745
欧拉回路
考虑欧拉回路有一个性质。
如果把点抽出来搞成一条直线，路径看成区间覆盖，那么一个点从左往右被覆盖的次数等于从右往左被覆盖的次数。
发现这个性质和本问题十分的相似，那么我们就想一下怎么欧拉回路解决。
考虑显然可以差分对吧，如果把红色的贡献看成，蓝色的看成，那么就可以差分了。
那么这个也等价于欧拉回路，接着考虑对于奇数点，两两之间匹配就好了。