问题重述

给定一个无向图（可能有自环？但看数据范围 $u≠v$ 应是无自环简单图）。每天，只能使用编号在 $[l_i, r_i]$ 范围内的边。问：只用这些边能否构成一个奇环？

奇环判定：在无向图中，存在奇环 ⇔ 图不是二分图。

核心思路

1. 二分图判定

用扩展域并查集：对每个点 $u$ 拆成两个点 $u$ 和 $u+n$，分别表示“点 $u$ 属于集合 0”和“点 $u$ 属于集合 1”。

对于一条边 $(u,v)$：

• 如果 $u$ 和 $v$ 在同一集合，则出现矛盾，说明有奇环。
• 否则，将 $(u,v+n)$ 和 $(v,u+n)$ 合并。

注意：这里代码中的实现略有不同，但思想一致。

2. 离线处理所有区间

暴力处理每个区间是 $O(Q \cdot M \cdot \alpha(N))$，不可行。

关键观察：固定左端点 $l$，随着右端点 $r$ 增大，图越来越稠密，一旦出现奇环，之后所有的 $r$ 都会满足条件。
即对每个 $l$，存在最小的 $r = f(l)$ 使得区间 $[l, r]$ 内的边构成非二分图。

那么对于询问 $[L,R]$：

• 如果 $f(L) \le R$，则答案为 YES（有奇环）。
• 否则答案为 NO。

3. 计算 $f(l)$ —— 用可撤销并查集+分治

目标：对每个 $l=1,2,\dots,m+1$ 计算最小的 $r$ 使得 $[l, r]$ 内有奇环。规定 $f(m+1)=m+1$。

用整体二分/分治的方法：

定义 solve(l, r, vl, vr)：

• 计算所有 $mid \in [l, r]$ 的 $f(mid)$，已知 $f(mid) \in [vl, vr]$。

步骤：

1. 取中点 $mid = (l+r)/2$。
2. 从 $mid$ 开始向右加边，直到出现奇环或到达 $vr$，得到 $f(mid)$。
3. 递归左半边 $[l,mid-1]$：已知右端点不会超过 $f(mid)$。
4. 递归右半边 $[mid+1,r]$：已知左端点从 $mid$ 开始，右端点从 $f(mid)$ 开始。

用可撤销并查集支持加边和回溯。

4. 复杂度分析

• 每个边在递归树中只会被加入常数次（类似线段树分治）。
• 每次操作 $O(\log N)$（并查集按秩合并）。
• 总复杂度 $O(M \log M \log N)$，可过 $2\times 10^5$。

代码详解

// 可撤销并查集
int fah[N*2], sz[N*2];
pair<int,int> stk[N*10];  // 记录合并操作
int top;

upd(id)：加边 $e[id]$，返回是否形成奇环。

核心分治函数：

solve(l, r, vl, vr) {
    mid = (l+r)/2;
    // 步骤1：加入[mid, min(vl,r)-1]的边（这些边对所有mid都适用）
    for i=mid to min(vl,r)-1: upd(i)
    
    // 步骤2：从max(mid,vl)开始向右加边，找到第一个奇环位置
    for i=max(mid,vl) to vr:
        if(upd(i)) { ans[mid]=i; break; }
    
    // 步骤3：撤销步骤2中加入的边（除了ans[mid]之前的）
    for i=max(mid,vl) to ans[mid]-1: undo()
    
    // 递归左半边 [l,mid-1]
    if(mid-1 < min(r,vl)) upd(mid-1)  // 左半边需要[mid-1]这条边
    solve(l,mid-1, vl, ans[mid])
    撤销临时加的边
    
    // 递归右半边 [mid+1,r]
    for i=max(vl,r) to ans[mid]-1: upd(i)  // 右半边需要这些边
    solve(mid+1, r, ans[mid], vr)
    撤销临时加的边
}

5. 处理询问

预处理后，ans[l] 表示左端点为 $l$ 时，最小的右端点使得有奇环。

对于询问 $[x,y]$，我们看 $x$ 为左端点时：

• 如果 $ans[x] \le y+x-1$（注意代码中坐标偏移），则 YES
• 否则 NO

坐标偏移说明：代码中 $e[m+i] = e[i]$ 是为了方便处理，实际询问区间是 $[x,y]$ 对应原边 $x..y$，但算法中处理的是 $[l,r]$ 对应 $e[l]..e[r]$。

样例分析

输入：

6 8 2
1 3
1 5
1 6
2 5
2 6
3 4
3 5
5 6
4 8
4 7

边1-8如上。询问：

1. [4,8]：看从边4开始，最早何时有奇环
2. [4,7]：同理

计算得：

• 对左端点4，最早在边8处有奇环 → 询问[4,8]：8≤8 → YES
• 询问[4,7]：8>7 → NO

输出：

NO
YES

总结

这道题的精髓在于：

1. 将“区间是否存在奇环”转化为“对每个左端点求最小右端点”。
2. 用整体二分+可撤销并查集高效计算所有 $f(l)$。
3. 利用单调性（右端点增大，更易出现奇环）优化。

时间复杂度 $O(M \log M \log N)$，空间 $O(N+M)$，能够处理 $2\times 10^5$ 的数据规模。