How do you use so many functions and manage to get under the TLE?

Sorry to disturb you,but could you explain how LCT in problem C worked.I do not understand your solution.

I compute the longest suffix of edge which can form a bipartite firstly,and then I try to add edge from prefix and remove the edge in the suffix to compute the array $$$Last$$$(the same as the $$$last[]$$$ in the tutorial).but it doesn't work,because some circle is ignored(maybe in these cycles,there is a circle of odd length).

Thank you very much.

Initially set all to the same color.

Let's say we want to add an edge from $$$u$$$ to $$$v$$$. Check if $$$u$$$ and $$$v$$$ are of the same parent(Are connected). If they are, then make sure their colors are different.

If they have different parents, Let's say $$$p$$$ and $$$q$$$ respectively, add an edge from $$$q$$$ to $$$p$$$ in the DSU(parent[q] = p). If their colors are the same, you want an additional mark on the edge which says to reverse the color.

When you want to get the color, go through all the edges leading to the parent, and change the color as you go along the edges if you need to reverse the color.

Look here

Sorry, it should be 200, I will fix it later.

Further, I think it should be possible to use path compression to improve the complexity somewhat, although I’m not sure it will help in practice.

The original reason for the $$$\log N$$$ factor is that path compression is not performed in the DSU because it “is impossible” with rollbacks. Of course, there’s nothing preventing one from implementing rollbacks of path compression, but the question is whether it such revertible path compression actually improves efficiency.

I can’t answer that. But for this particular problem, we can still improve the complexity by using path compression in a part of the solution that doesn’t require rollbacks:

Notice that the DSU operations corresponding to the right-hand-side edges are not disturbed by any rollbacks. (When a new block starts, we can rebuild the whole DSU from scratch. It is not necessary to roll back the previous block’s right-hand-side operations.) There are $$$M$$$ unions per block from the right-hand side. We can do those unions with path compression, for a total run-time of $$$M \alpha(N)$$$. Assuming revertible path compression is meaningless, we can do the left-hand-side operations without further path compression, at $$$\log N$$$ time per operation. The total time is then $$$M^2 \div B\, \alpha(N) + Q B \log N$$$ (down from $$$(M^2 \div B + Q B) \log N$$$), and equating the two terms to ensure neither dominates the other gives optimal $$$B = M \div \sqrt{Q \frac{\log N}{\alpha(N)}} \approx M \div \sqrt{Q \log N}$$$ with the grand total run-time $$$\mathrm{O}\left(\mathrm{sort}\ Q + M \sqrt{Q\, \alpha(N) \log N}\right)$$$.

Thanks, fixed!

When k is odd, do query of length k/2, and the problem size becomes at most k/2+1, which is acceptable. BTW the solution has missed a keypoint: let function begin be the startpoint index, then begin(n)=n/2+1-begin(n/2) when n is even, and begin(n)=n/2+2-begin(n/2+1) when n is odd.

See my code: https://codeforces.me/blog/entry/80490?#comment-669285

I don't use rollbacks for this subtask. Instead I maintain two DSUs. The first DSU (X) handles edges outside of [block left endpoint, r]. To handle the edges in [block left endpoint, l) I have a separate DSU (Y) where the vertices in Y are the connected components in X. Y gets reset between queries.