P7843

分治的妙妙题。

1. 题意

给定 $m$ 个双向的 2-SAT 限制（即 $u_i$ 选了 $x_i$ 则 $v_i$ 要选 $y_i$，同样 $v_i$ 选了 $y_i$ 则 $u_i$ 要选$x_i$），$q$ 次询问 $[l, r]$ 最少能划分成多少段有解的 2-SAT 限制。

$n\leq 10 ^ 5, m\leq 6\times 10 ^ 5, q\leq 10 ^ 6$，时限 2.5 s。

2. 思路

首先考虑如何判定 2-SAT 限制是否有解，发现这个 Tarjan 实质是在求联通分量（因为有双向边，联通分量一定是强连通分量）。

那么，我们可以使用一个并查集维护联通性，如果一次之后出现了 $u_i$ 和 $u_i$ 的反面在一个强连通分量，则不合法。

如何求一个区间最少划分成多少个有解的 2-SAT 问题？这个可以简单的贪心，预处理每一个限制一直向右扩展到哪一处开始不合法（显然不合法之后不可能再合法），前面的显然划为一段，如此贪心。这个贪心过程可以使用倍增优化，也就是说，如果我们能找到从一个限制一直向右扩展到哪一处开始不合法，我们可以倍增跳，做到 $O(q\log n)$ 的复杂度，显然已经足够了。问题在于如何求哪一处开始不合法。

记 $f(i)$ 为极短的 $[i, f(i)]$ 为无解的限制，这个就类似一个 DP 了。我们发现似乎没有什么方法可以做到比较优的复杂度，因为这个和一般的 DP 又不尽相同。

考虑 $f(i)$ 的性质，我们发现，$f(i)$ 显然是具有单调性的，这启示我们向 DP 的决策单调性的方向思考。

类似于决策单调性的求法，我们考虑二分，solve(l, r, sl, sr) 表示处理 $[l, r]$ 之间的$f(i)$，已知答案区间为 $[sl, sr]$。直接计算 $f(mid)$，然后向下递归即可。

如何计算 $f(mid)$，如果我们暴力向右扩展的话，其实复杂度是错误的。回顾决策单调性的写法与时间复杂度的证明，我们取的时候，必须只能在 $[sl, sr]$ 之间计算，也就是说，我们的时间复杂度应只与 $sr - sl$ 有关。但是这个题，我们发现，如果 $mid < sl$，即使我们知道答案不会出现在这一段区间，我们还是得扫一遍，为后面判断做铺垫，而这造成了错误，使得复杂度不对。如何处理他呢？

感觉上，这个东西应该是留给上一层计算才对，于是我们强制要求在 $[r + 1, sl - 1]$ 之间的限制已经被加入并查集了。这样才能保证我们计算的时候，不会进入多余的无用的计算。递归结束时显然要撤回，所以用可撤销并查集，预处理时间复杂度 $O(m\log m\log n)$，总时间复杂度为 $O(m\log m\log n + q\log n)$。至于为什么不将 $[mid, sl - 1]$ 或是 $[l, sl - 1]$ 加入并查集，是因为这不是 $[l, r]$ 所有节点所必需的，所以先不管。具体在实现部分讲。

3. 实现

这个题由于要保证 $[r + 1, sl - 1]$ 的在进入该层前已经加入了并查集了，所以我们注意我们如果要计算 $f(mid)$，要先将 $[mid, \min\{r, sl - 1\}]$ 的加入，然后再从 $sl$ 向右扫。如果要向左区间递归，那么 $[mid, sl - 1]$ 的保留（因为向 $[l, mid - 1]$ 递归），所以我们要将第一次加入的边保留。而向右区间，则是 $[r, f(mid) - 1]$，这个直接实现即可。

考虑复杂度，同整体二分，$O(m\log m)$，加上可撤销并查集，$O(m\log m\log n)$，可以通过。

注意可能前面上层的就已经不合法了，所以要将前面是否合法并向下递归。还要注意判断自相矛盾的情况。可能比较难写，放一个二分的代码。（到底是什么二分 / 分治呢？

struct DSU {  } dsu ;

bool check(int x) { return dsu.find(x) != dsu.find(x ^ 1); }

void solve(int l, int r, int sl, int sr, bool frm)
{
	// printf("Solve [%d, %d] : [%d, %d]\n", l, r, sl, sr);
	if (l > r) return;
	if (sl == sr) {
		for (int i = l; i <= r; ++ i) f[i] = sl;
		return;
	}
	int mid = (l + r) >> 1, now = frm, st = dsu.top;
	for (int i = mid; i <= r && i < sl; ++ i) {
		dsu.merge(opt[i].first, opt[i].second);
		dsu.merge(opt[i].first ^ 1, opt[i].second ^ 1);
		now &= check(opt[i].first);
	}
	int bac = dsu.top, ls = now;
	for (int i = std::max(sl, mid); i <= sr; ++ i) {
		dsu.merge(opt[i].first, opt[i].second);
		dsu.merge(opt[i].first ^ 1, opt[i].second ^ 1);
		now &= check(opt[i].first);
		if (!now) {
			f[mid] = i;
			break;
		}
	}
	if (now) {
		for (int i = mid; i <= r; ++ i) f[i] = m + 1;
		dsu.back(bac);
		return solve(l, mid - 1, sl, sr, ls), dsu.back(st);
	}
	dsu.back(bac), solve(l, mid - 1, sl, f[mid], ls);
	dsu.back(st), now = frm;
	for (int i = std::max(sl, r + 1); i < f[mid]; ++ i) {
		dsu.merge(opt[i].first, opt[i].second);
		dsu.merge(opt[i].first ^ 1, opt[i].second ^ 1);
		now &= check(opt[i].first);
	}
	solve(mid + 1, r, f[mid], sr, now), dsu.back(st);
}

int main()
{
    solve(1, m, 1, m + 1, 1);
    return 0;
}