想要更好的阅读体验？

T1

简化题意:给序列$A,B(|A|=|B|=n)$和$m$种操作,1操作可以让$u_i,v_i$都+1或-1,2操作可以让$u_i+1,v_i-1$或$u_i-1,v_i+1$,问能否让$A=B$

$n,m\le 10^5$

如果让$u+1$且$u,v$间有2操作,则可以使用2操作让$u-1,v+1$,即对$u$的+1操作转移到$v$上.也就是说,对于由2操作构成的连通块$S$,对任何一个点$x\in S$的+1操作都能转移到另一个点$y\in S$上.因此将整个联通块看成一个点(显然可以并查集做到,以下的点都指这些点).点权为$\sum_{x\in S}b_i-a_i$.

此时问题转化为,只有1操作(可以将其看作无向边),能否让所有点点权为0.

考虑一个奇环$R$,对$u,v\in R$执行1操作,可以让任意两点$x,y\in R$都+1或-1.所以对于非二分图连通块$G$,若$\sum_{S\in G}W_S$为偶数则可以做到,否则不能.对于二分图连通块$G$,若$\sum_{S\in G}W_S=0$则可以做到.

时间复杂度$O((n+m)\log n)$,这个log是路径压缩的并查集的.

code