Joker
Contest: Baltic Olympiad in Informatics 2020, Day 1 (IOI, Unofficial Mirror Contest, Unrated)
Difficulty rating: 2800
Tags: *special, bitmasks, data structures, divide and conquer, dsu

Joker returns to Gotham City to execute another evil plan. In Gotham City, there are $$$N$$$ street junctions (numbered from $$$1$$$ to $$$N$$$) and $$$M$$$ streets (numbered from $$$1$$$ to $$$M$$$). Each street connects two distinct junctions, and two junctions are connected by at most one street.

For his evil plan, Joker needs to use an odd number of streets that together form a cycle. That is, for a junction $$$S$$$ and an even positive integer $$$k$$$, there is a sequence of junctions $$$S, s_1, \ldots, s_k, S$$$ such that there are streets connecting (a) $$$S$$$ and $$$s_1$$$, (b) $$$s_k$$$ and $$$S$$$, and (c) $$$s_{i-1}$$$ and $$$s_i$$$ for each $$$i = 2, \ldots, k$$$.

However, the police are controlling the streets of Gotham City. On each day $$$i$$$, they monitor a different subset of all streets with consecutive numbers $$$j$$$: $$$l_i \leq j \leq r_i$$$. These monitored streets cannot be a part of Joker's plan, of course. Unfortunately for the police, Joker has spies within the Gotham City Police Department; they tell him which streets are monitored on which day. Now Joker wants to find out, for some given number of days, whether he can execute his evil plan. On such a day there must be a cycle of streets, consisting of an odd number of streets which are not monitored on that day.

Input format:
The first line of the input contains three integers $$$N$$$, $$$M$$$, and $$$Q$$$ ($$$1 \leq N, M, Q \leq 200\,000$$$): the number of junctions, the number of streets, and the number of days to be investigated. The following $$$M$$$ lines describe the streets. The $$$j$$$-th of these lines ($$$1 \le j \le M$$$) contains two junction numbers $$$u$$$ and $$$v$$$ ($$$u \neq v$$$), saying that street $$$j$$$ connects these two junctions. It is guaranteed that any two junctions are connected by at most one street. The following $$$Q$$$ lines contain two integers $$$l_i$$$ and $$$r_i$$$, saying that all streets $$$j$$$ with $$$l_i \leq j \leq r_i$$$ are checked by the police on day $$$i$$$ ($$$1 \leq i \leq Q$$$).

Output format:
Your output is to contain $$$Q$$$ lines. Line $$$i$$$ ($$$1 \leq i \leq Q$$$) contains "YES" if Joker can execute his plan on day $$$i$$$, or "NO" otherwise.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Scoring:
Subtasks:

1. (6 points) $$$1 \leq N, M, Q \leq 200$$$
2. (8 points) $$$1 \leq N, M, Q \leq 2\,000$$$
3. (25 points) $$$l_i = 1$$$ for $$$i = 1, \ldots, Q$$$
4. (10 points) $$$l_i \leq 200$$$ for $$$i = 1, \ldots, Q$$$
5. (22 points) $$$Q \leq 2\,000$$$
6. (29 points) No further constraints

The graph in the example test:

Example input:
6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
4 7

Example output:
NO
YES

Editorial:
In this task, you are given a graph with $$$N$$$ nodes and $$$M$$$ edges. Furthermore, you are required to answer $$$Q$$$ queries. In every query, all the edges from the interval $$$[l_i,r_i]$$$ are temporarily removed and you should check whether the graph contains an odd cycle or not.
Thanks for the solutions to the Germany (Subtasks 1-5) and Poland (Subtask 6) BOI teams.
Subtask 1 ($$$N, M, Q \leq 200$$$) For every query do a DFS from every node and check if an odd cycle is formed.
Complexity: $$$O(QNM)$$$.
Subtask 2 ($$$N, M, Q \leq 2000$$$)
The graph is bipartite if and only if it contains no odd cycle. Therefore we can color the nodes with two colors (with DFS or BFS) and check if two adjacent nodes share the same color or not.
Complexity: $$$O(QM)$$$.
Subtask 3 ($$$l_i=1$$$ for all queries)
We can sort the queries by their right endpoints ($$$r_i$$$) and answer them offline. Therefore we insert all the edges in the decreasing order of their indices into a DSU structure.
Complexity: $$$O(Q \log Q +M \alpha(N))$$$.
Subtask 4 ($$$l_i \leq 200$$$ for all queries)
We can sort the queries by their left endpoint ($$$l_i$$$) and apply our solution from Subtask 3 to all queries with the same $$$l_i$$$.
Complexity: $$$O(Q \log Q + 200 M \alpha(N))$$$.
Subtask 5 ($$$Q \leq 2000$$$)
We use the "Mo's algorithm" technique. Split the range $$$[1, M]$$$ of edge indices into blocks of size $$$B$$$ and sort the queries by $$$l_i/B$$$ or by $$$r_i$$$ if their left endpoint is in the same block. We can now keep two pointers to hold the current range of removed edges. If we answer all queries in the current block, the right pointer moves at most $$$M$$$ steps. The left pointer moves at most $$$QB$$$ steps in total. Since the left pointer may move to the left and the right inside the current block we need to modify our DSU to allow rollbacks. If we choose $$$B = M / \sqrt Q$$$ we get the following runtime:
Complexity: $$$O(Q \log Q + M \sqrt Q \log N)$$$.
Subtask 6 (no further constraints)
For any $$$1 \leq l \leq M$$$, let $$$\mathrm{last}[l]$$$ be the last index $$$r$$$ such that the answer for the query $$$[l, r]$$$ is positive (or $$$M+1$$$ if no such index exists). That is, the graph exluding the edges $$$[l,r]$$$ is bipartite, but the graph excluding the edges $$$[l,r-1]$$$ is not. We can prove that if $$$l_1 < l_2$$$, then $$$\mathrm{last}[l_1] \leq \mathrm{last}[l_2]$$$. We will exploit this fact in order to compute the array $$$\mathrm{last}$$$ using a divide & conquer algorithm.
We write a recursive function $$$\mathrm{rec}$$$, which takes two intervals: $$$[l_1, l_2], [r_1, r_2]$$$ ($$$1 \leq l_1 \leq l_2 \leq M$$$, $$$1 \leq r_1 \leq r_2 \leq M+1$$$), possibly intersecting, but $$$l_1 \leq r_1$$$ and $$$l_2 \leq r_2$$$. This function will compute $$$\mathrm{last}[l]$$$ for each $$$l \in [l_1, l_2]$$$, assuming that for these values of $$$l$$$, we have $$$\mathrm{last}[l] \in [r_1, r_2]$$$. We will initially call $$$\mathrm{rec}([1, M], [1, M+1])$$$.
We assume that when $$$\mathrm{rec}([l_1, l_2], [r_1, r_2])$$$ is called, then our DSU contains all edges with indices to the left of $$$l_1$$$ and to the right of $$$r_2$$$. For instance, when $$$M=9$$$ and $$$\mathrm{rec}([2, 5], [3, 7])$$$ is called, then edges with indices $$$1$$$, $$$8$$$, and $$$9$$$ should be in the DSU. We also assume that the graph in the DSU is bipartite.
We take $$$l_{\mathrm{mid}} := (l_1 + l_2) / 2$$$ and compute $$$\mathrm{last}[l_{\mathrm{mid}}]$$$; this can be done by adding all edges $$$[l_1, l_{\mathrm{mid}}-1]$$$ to the DSU, and then trying to add all edges with indices $$$r_2, r_2-1, r_2-2, \ldots$$$, until we try to add an edge breaking the bipartiteness. The index $$$r_{\mathrm{mid}}$$$ of such an edge is exactly $$$\mathrm{last}[l_{\mathrm{mid}}]$$$. We then rollback all edges added so far in our recursive call.
Now that we know that $$$\mathrm{last}[l_{\mathrm{mid}}] = r_{\mathrm{mid}}$$$, we will run two recursive calls:
• For each $$$l \in [l_1, l_{\mathrm{mid}}-1]$$$, we know that $$$\mathrm{last}[l] \in [r_1, r_{\mathrm{mid}}]$$$. We run $$$\mathrm{rec}([l_1, l_{\mathrm{mid}}-1], [r_1, r_{\mathrm{mid}}])$$$, remembering to add all necessary edges to the right of $$$r_{\mathrm{mid}}$$$. After the recursive call, we rollback them.
• For each $$$l \in [l_{\mathrm{mid}}+1, l_2]$$$, we know that $$$\mathrm{last}[l] \in [r_{\mathrm{mid}}, r_2]$$$. We run $$$\mathrm{rec}([l_{\mathrm{mid}}+1, l_2], [\max(l_{\mathrm{mid}}+1, r_{\mathrm{mid}}), r_2])$$$, now adding all necessary edges to the left of $$$l_{\mathrm{mid}}+1$$$. We rollback them after the recursive call.
We can see that each recursive call uses at most $$$O((l_2-l_1) + (r_2-r_1))$$$ edge additions and rollbacks in DSU, each taking $$$O(\log N)$$$ time pessimistically. Also, on each level of recursion, the total length of all intervals is bounded by $$$2M$$$. Hence, all intervals in all recursive calls have total length bounded by $$$O(M \log M)$$$. Hence, the total time of the preprocessing is $$$O(M \log M \log N)$$$.
With our preprocessing, each query $$$[l, r]$$$ reduces to simply verifying $$$r \leq \mathrm{last}[l]$$$, which can be done in constant time.
Complexity: $$$O(M \log M \log N + Q)$$$.