終于有能拿出來的東西了。

upd：后來得知這個叫 baka's trick。

最初的問題
題意轉化之后是雙指針，每次加一條邊，查詢連通性，刪除最早的邊。
標準做法是 動態圖完全連通性。

但是繼續觀察，此題提供了兩個特殊性質。

1. 保證圖為森林。
2. 每次刪邊只刪最早的。

基于性質 1 自然可以得到 LCT 的做法，也就是大多數題解的做法。
下面提出一種基于性質 2 的算法。

先描述一下問題：

維護 \(n\) 個點和一個隊列，支持一下操作：
1 a b 在隊列末尾加入一條無向邊 \((a, b)\)。
2 刪除隊列首。
3 a b 查詢只考慮隊列中的邊的情況下，\(a, b\) 兩點是否連通。
強制在線。

連通性問題首選并查集。
帶刪邊就用可撤銷并查集。
然而可撤銷并查集的結構類似于棧（只能刪除最后加入的元素）

分塊算法

我們對邊序列進行分塊。
維護隊列其實也就相當于是維護雙指針（單調）
考慮若目前的兩個指針分別為 \(l, r\)。
\(l\) 在第 \(B\) 個塊里。

我們先從第 \(B+1\) 個塊開始順次插入邊，直到 \(r\)。
然后再從第 \(B\) 個塊末尾開始倒序插入邊，直到 \(l\)。
這樣 \(l\) 就是最后被插入的邊了。

考慮左刪除，直接刪即可。
若 \(l\) 跑到了下一個塊，就暴力重構所有邊。
考慮右插入，我們先將第 \(B\) 個塊的邊全部刪除，再插入新的邊，然后再把第 \(B\) 個塊的邊插回來。
容易發現每一步 插入/刪除 的次數均不超過 \(O(\sqrt n)\)。

復雜度達到 \(O(n^{1.5}\log n)\)。

線段樹算法

容易發現上述算法的本質就是調整了插入并查集的邊的順序，使得插入和刪除都比較容易。
那么能否使用分治結構實現？

Lemma：在線段樹上用 \(O(\log n)\) 個節點表示一個區間時，位于每一層上面的節點至多只有 2 個。

顯然，這個涉及到線段樹區間操作復雜度的證明。
分類討論遞歸情況即可。

我們提出以下結構維護：
若目前的左右指針為 \(l, r\)，則在線段樹上劃分出來 \(O(\log n)\) 個小區間表示 \([l, r]\)。
隨后按照深度從小到大的方式依次插入這些小區間。

首先，容易發現在指針掃過去的過程中，線段樹上的每個節點至多被加入一次刪除一次。
加入/刪除 的時候，均需要先把深度更大的節點刪除，而后再加回來。
我們知道 \(T(n) = T(\frac{n}{2}) + O(n)\)，\(T(n) = O(n)\)。
也就是深度更大的那些節點的 \(size\) 的和與這個節點的大小同階。
那么我們就可以放心操作了，因為復雜度上等價于只刪除了這個節點。
總的 插入/刪除 次數 \(O(n \log n)\)。
復雜度 \(O(n \log^2 n)\)。

倍增算法

線段樹算法的實現較為困難，且難以拓展。
下面提出一種基于倍增實現的算法，理論上可以實現雙端隊列。
（即隊列首尾同時插入刪除）

考慮一種有 \(O(\log n)\) 層的結構，其中第 \(i\) 層能夠存儲 \(2^i\) 個元素。
插入就直接扔到第 \(0\) 層，若超出這層的容量限制就全部扔到上面一層。
容易發現這個結構類似于二進制分組。

現在我們維護兩個這種結構 \(A, B\)。
插入并查集時仍然是先插大的層后插小的層。
新的邊只插入 \(B\)，刪除時只刪除 \(A\)。
若 \(A\) 目前為空，則從 \(B\) 中找到元素最多的層（容易發現一定是最早被插入的若干個元素）而后直接轉移到 \(B\) 中。
刪除無非就是插入的逆過程。

上述結構與線段樹類似，但是更容易維護。
復雜度 \(O(n \log^2 n)\)。

再考慮如果改成首尾均插入/刪除怎么辦。
直接刪的話復雜度會假。
我們采用經典倍縮策略，第 \(i\) 層的大小縮減到 \(2^{i - 1}\) 以下才向下合并。
也就是超過 \(2^i\) 向上合并，低于 \(2^{i - 1}\) 向下合并。
這樣刪除操作也可以均攤分析。

倍增版實現

提交記錄。

namespace mset
{
	const int sz1 = 400005, sz2 = 200005;
	int fa[sz1], siz[sz1];
	int sta[sz2];

	void init(int n)
	{
		for (int i = 1; i <= n; ++i)
			fa[i] = i;
		for (int i = 1; i <= n; ++i)
			siz[i] = 1;
	}
	
	int find(int a)
	{
		while (a != fa[a])
			a = fa[fa[a]];
		return a;
	}

	void net(int a, int b)
	{
		a = find(a); b = find(b);
		if (siz[a] < siz[b])
			swap(a, b);
		sta[++sta[0]] = b;
		fa[b] = a; siz[a] += siz[b];
	}

	void bak(int a)
	{
		while (a --> 0)
		{
			int x = sta[sta[0]--];
			siz[fa[x]] -= siz[x];
			fa[x] = x;
		}
	}
}

namespace quegraph
{
	const int B = 19;
	const int sz = 200005;
	struct node
	{
		int a, b;
	};
	int now, ano;
	node tmp[sz];
	node *rt = tmp, *lf = rt - 1;

	void init(int n)
	{
		mset::init(n);
	}

	void reinsertr(int i)
	{
		for (int j = now & ~((1 << i + 1) - 1), k = j ^ 1 << i; j < k; ++j)
			mset::net(rt[j].a, rt[j].b);
	}

	void reinsertl(int i)
	{
		for (int j = ano & ~((1 << i + 1) - 1), k = j ^ 1 << i; j < k; ++j)
			mset::net(lf[-j].a, lf[-j].b);
	}

	void insert(int a, int b)
	{
		int x = __builtin_ctz(now + 1);
		int sum = (1 << x) - 1 + (ano & (1 << x) - 1);
		mset::bak(sum);
		rt[now].a = a; rt[now].b = b; ++now;
		reinsertr(x);
		for (int i = x - 1; i >= 0; --i)
			if (ano & 1 << i)
				reinsertl(i);
	}

	void del()
	{
		if (ano == 0)
		{
			int x = __lg(now), y = 1 << x;
			now ^= y; ano = y;
			rt += y; lf += y;
		}
		int sum = 0, x = __builtin_ctz(ano);
		sum = (1 << x) + (now & (1 << x + 1) - 1);
		mset::bak(sum); --ano;
		if (now & 1 << x)
			reinsertr(x);
		for (int i = x - 1; i >= 0; --i)
		{
			reinsertl(i);
			if (now & 1 << i)
				reinsertr(i);
		}
	}
}

后記

后來在 UOJ 發現原題。
題目鏈接。
做法完全一致。

在 最小差值生成樹 這道題上拿到最優解。
提交記錄。