下面是本题在网上的一篇题解。

原题链接 这是一道有(du)趣(liu)的数据结构题

首先发现无修改询问，所以珂以莫队。然后发现你要维护当前的图是否为二分图，这显然珂以大力LCT维护最大生成树。然后复杂度就变成了惊人的$O(N\sqrt N\log N)$，附加大常数惊喜。显然，不加任何卡常技巧，这是过不去的；用了许多卡常技巧，这也是过不去的。

我们必须考虑换个路子。观察一下Subtask$3$，珂以发现当询问中的$l$为常数时，有一个临界值$r$，使得：$\forall k\in [l,r)$，询问$(l,k)$对应的图不是二分图；$\forall k\in [r,m]$，询问$(l,k)$对应的图是二分图。所以这个Subtask便珂以预处理出这个临界值，这显然珂以用LCT在$O(N\log N)$内实现。

我们把上述对于$l$的临界值定义为$A_l$。进一步思考，我们会发现：$\forall l_1\le l_2$，不等式$A_{l_1}\le A_{l_2}$恒成立，即数组$A$是单调不减的。又由于LCT支持加边和删边，于是，我们珂以双指针来预处理出数组$A$。这样复杂度依旧是优秀的$O(N\log N)$，珂以通过所有Subtask。

Q: 窝不会LCT肿么办？

A: 那就用那个不用LCT的做法呗。

不用LCT是什么做法？我们珂以发现，LCT在上述算法中，只是来维护最大生成树，判断二分图的。那为什么上述算法中LCT是必要的呢？因为在双指针的过程中，我们要在加边和删边的操作之余判断二分图，当加边和删边无任何顺序时，LCT是必要的。

那么不用LCT的做法，就是要让加边和删边的操作有顺序，即每一次加边时把这个边放入一个栈里，删边时就弹栈。这时删边操作就变成了回滚操作。于是我们珂以用常数较小的可撤销并查集来代替常数巨大的LCT。

然而，双指针并不能用一个栈来维护。于是我们珂以考虑分治：定义分治函数$S$维护四个值$l,r,L,R$，其中前提条件满足$\forall i\in[l,r],A_i\in[L,R]$，且在调用$S(l,r,L,R)$时，可撤销并查集内已有$[1,l-1]\cup [r+1,m]$内的所有边。设$M=(l+r)/2$，则珂以先在$O(n)$内算出$A_M$。这时$\forall i\in[l,M-1],A_i\le A_M$，且$\forall i\in [M+1,r],A_i\ge 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(N\log^2 N)$。因为常数较小，所以跑得和LCT的$O(N\log N)$差不多快。

代码？不存在的。

我有几个疑惑。
1.为什么调用$S(l,r,L,R)$时，可撤销并查集内要有$[1,l-1]\cup [r+1,m]$内的所有边？
2.怎么在$O(n)$内算出$A_M$，加哪些边？