T1
简化题意:给序列A,B(|A|=|B|=n)和m种操作,1操作可以让ui,vi都+1或-1,2操作可以让ui+1,vi−1或ui−1,vi+1,问能否让A=B
n,m≤105
如果让u+1且u,v间有2操作,则可以使用2操作让u−1,v+1,即对u的+1操作转移到v上.也就是说,对于由2操作构成的连通块S,对任何一个点x∈S的+1操作都能转移到另一个点y∈S上.因此将整个联通块看成一个点(显然可以并查集做到,以下的点都指这些点).点权为∑x∈Sbi−ai.
此时问题转化为,只有1操作(可以将其看作无向边),能否让所有点点权为0.
考虑一个奇环R,对u,v∈R执行1操作,可以让任意两点x,y∈R都+1或-1.所以对于非二分图连通块G,若∑S∈GWS为偶数则可以做到,否则不能.对于二分图连通块G,若∑S∈GWS=0则可以做到.
时间复杂度O((n+m)logn),这个log是路径压缩的并查集的.
Orz万巨巨太强了