原题链接
这是一道有(du)趣(liu)的数据结构题
首先发现无修改询问，所以珂以莫队。然后发现你要维护当前的图是否为二分图，这显然珂以大力LCT维护最大生成树。然后复杂度就变成了惊人的(O(Nsqrt Nlog N))，附加大常数惊喜。显然，不加任何卡常技巧，这是过不去的；用了许多卡常技巧，这也是过不去的。
我们必须考虑换个路子。观察一下Subtask(3)，珂以发现当询问中的(l)为常数时，有一个临界值(r)，使得：(forall kin [l,r))，询问((l,k))对应的图不是二分图；(forall kin [r,m])，询问((l,k))对应的图是二分图。所以这个Subtask便珂以预处理出这个临界值，这显然珂以用LCT在(O(Nlog N))内实现。
我们把上述对于(l)的临界值定义为(A_l)。进一步思考，我们会发现：(forall l_1le l_2)，不等式(A_{l_1}le A_{l_2})恒成立，即数组(A)是单调不减的。又由于LCT支持加边和删边，于是，我们珂以双指针来预处理出数组(A)。这样复杂度依旧是优秀的(O(Nlog N))，珂以通过所有Subtask。
Q: 窝不会LCT肿么办？
A: 那就用那个不用LCT的做法呗。
不用LCT是什么做法？我们珂以发现，LCT在上述算法中，只是来维护最大生成树，判断二分图的。那为什么上述算法中LCT是必要的呢？因为在双指针的过程中，我们要在加边和删边的操作之余判断二分图，当加边和删边无任何顺序时，LCT是必要的。
那么不用LCT的做法，就是要让加边和删边的操作有顺序，即每一次加边时把这个边放入一个栈里，删边时就弹栈。这时删边操作就变成了回滚操作。于是我们珂以用常数较小的可撤销并查集来代替常数巨大的LCT。
然而，双指针并不能用一个栈来维护。于是我们珂以考虑分治：定义分治函数(S)维护四个值(l,r,L,R)，其中前提条件满足(forall iin[l,r],A_iin[L,R])，且在调用(S(l,r,L,R))时，可撤销并查集内已有([1,l-1]cup [r+1,m])内的所有边。设(M=(l+r)/2)，则珂以先在(O(n))内算出(A_M)。这时(forall iin[l,M-1],A_ile A_M)，且(forall iin [M+1,r],A_ige A_M)。所以珂以在(S(l,r,L,R))中调用(S(l,M-1,L,A_M))和(S(M+1,r,A_M,R))。注意要在调用之前往可撤销并查集内插入相应的边，然后在调用结束后回滚掉。又因为(S)调用中区间的总长度为(O(N))级别，再加上可撤销并查集的(O(log N))，所以时间复杂度为(O(Nlog^2 N))。因为常数较小，所以跑得和LCT的(O(Nlog N))差不多快。
代码？不存在的。