首先我在做 CF19E 这道题，数据范围只有 $10^4$，于是我写了个线段树分治，结果 TLE 了。

然后我就想肯定是我复杂度写假了嘛，然后就把代码改了改（只改了主函数），交到了模板题上，结果过了，并且跑得飞快。

更离谱的事情在于，模板题的数据范围是 $\color{red}10^5$ 的，甚至比 CF 那道题的 $\color{green}10^4$ 大十倍，但前者过了后者却没过。

接着我在本地随机了一组模板题的数据（输出是全 Yes），结果慢到离谱，也就是说洛谷过了但本地没跑过。

灵异的来了，于是我测了一下并查集里 get 函数内 while 循环的运行次数（变量 QwQ），结果当 $n=k=10^4,m=2\times10^4$ 时，整整运行了 $\color{red}179275815$ 次；当 $n,k,m$ 整体翻倍时，整整运行了 $\color{red}819972842$ 次！这说明这份代码的复杂度可能退化至了 $\mathcal O(n^2)$ 乃至更高，但这样的代码却在洛谷上通过了。

所以这份代码的问题在哪？以及它为什么能在洛谷上通过/为什么在本地和 CF 会 TLE？

P5787 的代码：

//#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, k, u[N], v[N], fa[N], siz[N], top, stk[N], QwQ;
basic_string<int> vec[N << 2];
void upd(int p, int l, int r, int L, int R, int x) {
	if (L <= l && r <= R) return vec[p] += x, void();
	int mid = l + r >> 1;
	if (L <= mid) upd(p << 1, l, mid, L, R, x);
	if (R > mid) upd(p << 1 | 1, mid + 1, r, L, R, x);
}
int get(int x) { while (x != fa[x]) x = fa[x], QwQ++; return x; }
void merge(int x, int y) {
	if (siz[x] > siz[y]) swap(x, y);
	fa[x] = y, siz[y] += siz[x], stk[++top] = x;
}
void solve(int p, int l, int r) {
	int tmp = top, flg = 1;
	for (int i : vec[p]) {
		int _u = get(u[i]), _v = get(v[i]);
		if (_u == _v) { flg = 0; break; }
		merge(_u, get(v[i] + n)), merge(_v, get(u[i] + n));
	}
	if (flg) {
		if (l == r) cout << "Yes\n";
		else {
			int mid = l + r >> 1;
			solve(p << 1, l, mid), solve(p << 1 | 1, mid + 1, r);
		}
	} else for (int i = l; i <= r; i++) cout << "No\n";
	while (top > tmp) { int x = stk[top--]; siz[fa[x]] -= siz[x], fa[x] = x; }
}
int main() {
//	freopen("dwd.in", "r", stdin), freopen("dwd.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m >> k;
	for (int i = 1, l, r; i <= m; i++) {
		cin >> u[i] >> v[i] >> l >> r;
		if (l < r) upd(1, 1, k, l + 1, r, i);
	}
	for (int i = 1; i <= n << 1; i++) fa[i] = i, siz[i] = 1;
	solve(1, 1, k);
	cerr << QwQ;
}

随机数据生成器：

#include <bits/stdc++.h>
using namespace std;
const int n = 2e4, m = 4e4, k = 2e4;
int main() {
	freopen("dwd.in", "w", stdout);
	cout << n << ' ' << m << ' ' << k << '\n';
	mt19937 rnd(time(0));
	for (int i = 1, u, v, l, r; i <= m; i++) {
		u = rnd() % (n >> 1) + 1, v = (n >> 1) + rnd() % (n + 1 >> 1) + 1;
		l = rnd() % k + 1, r = rnd() % k + 1;
		if (l > r) swap(l, r);
		cout << u << ' ' << v << ' ' << l << ' ' << r << '\n';
	}
}

CF19E 的代码：

#pragma GCC optimize(2, 3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 5;
int n, m, u[N], v[N], fa[N], siz[N], tot, ans[N];
stack<int> stk;
vector<int> vec[N << 1];
void upd(int p, int l, int r, int L, int R, int x) {
	if (L <= l && r <= R) return vec[p].emplace_back(x), void();
	int mid = l + r >> 1;
	if (L <= mid) upd(p << 1, l, mid, L, R, x);
	if (R > mid) upd(p << 1 | 1, mid + 1, r, L, R, x);
}
int get(int x) { return x == fa[x] ? x : get(fa[x]); }
void merge(int x, int y) {
	if (siz[x] > siz[y]) swap(x, y);
	fa[x] = y, siz[y] += siz[x], stk.push(x);
}
void solve(int p, int l, int r) {
	int tmp = stk.size(), flg = 1;
	for (int i : vec[p]) {
		int _u = get(u[i]), _v = get(v[i]);
		if (_u == _v) { flg = 0; break; }
		merge(_u, get(v[i] + n)), merge(_v, get(u[i] + n));
	}
	if (flg) {
		if (l == r) ans[++tot] = l;
		else {
			int mid = l + r >> 1;
			solve(p << 1, l, mid), solve(p << 1 | 1, mid + 1, r);
		}
	}
	while (stk.size() > tmp) { int x = stk.top(); stk.pop(), siz[fa[x]] -= siz[x], fa[x] = x; }
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> u[i] >> v[i];
		if (i > 1) upd(1, 1, m, 1, i - 1, i);
		if (i < m) upd(1, 1, m, i + 1, m, i);
	}
	for (int i = 1; i <= n << 1; i++) fa[i] = i, siz[i] = 1;
	solve(1, 1, m);
	cout << tot << '\n';
	for (int i = 1; i <= tot; i++) cout << ans[i] << ' ';
}