CF1375H Set Merging

一道平衡规划分析复杂度的题目。

题意：你开始有 $n$ 个集合 $\{a_1\}, \{a_2, \}\cdots, \{a_n\}$，其中 $a_1, a_2, \cdots, a_n$ 是一个排列。你可以合并两个集合 $A$ 和 $B$，但需要保证 $\max(A)<\min(B)$。注意合并之后 $A$ 和 $B$ 仍然存在。给定 $q$ 次询问 $[l, r]$，你需要合并出一个 $\{a_l, a_{l + 1},\cdots, a_r\}$，并输出编号。$n\leq 2 ^ {12}, q\leq 2 ^ {16}$，要求最后集合总数不超过 $2.2\times 10 ^ 6$。

先不考虑复杂度，我们直接考虑合并出所有答案：建一个值域线段树，计算当值域区间为 $[l, r]$，询问区间为 $[ql, qr]$ 时的答案，输出的编号显然是 $[1, n]$ 的答案。直接考虑在线段树上合并，将 $[l, mid]$ 和 $[mid + 1, r]$ 的答案合并起来。

这样其实是 $O(nq)$ 的，但是大家肯定都能想到将所有在一个节点的询问记忆化一下，还可以把 $[l, r]$ 区间离散化到当前节点所对应所有位置的集合再记忆化。

等你码完之后，你小心翼翼地写好提交，正准备迎接 Wrong Answer 的事实时，却发现过了！（如果你没有被卡常的话

下面考虑分析复杂度。假设 $d = \lceil\log_2 q\rceil, t = \lceil\log_2 n\rceil$，对于下面的 $\dfrac d2$ 层，假设所有的询问能将这些所有层的所有区间卡满，这一部分就是：

$$cost = \sum_{i = 0} ^ {\frac d2}2 ^ {t - i} 2 ^ {2i} = 2 ^ {t + \frac d2} = O(n\sqrt q)$$

其中第一部分表示节点个数，第二部分表示每一个节点所有的子区间。

对于上面的 $t - \dfrac d2$ 层，由于一次询问最多只能覆盖一个节点的一个区间，于是这一部分就是：

$$cost = 2 ^ {t - \frac d2}q = 2 ^ {t + \frac d2} = O(n\sqrt q)$$

于是最多只会合并出 $O(n\sqrt q)$ 个区间，在本题数据范围下为 $10 ^ 6$，实际运行为 $1.7\sim 2.0 \times 10 ^ 6$，可以通过。

void build(int x, int l, int r)
{
	tr[x] = {l, r, std::vector<int>(r - l + 1)};
	if (l == r) return void(tr[x].allid.front() = nw[l]);
	int mid = (l + r) >> 1;
	build(x << 1, l, mid), build(x << 1 | 1, mid + 1, r);
	auto &v1 = tr[x << 1].allid, &v2 = tr[x << 1 | 1].allid;
	std::merge(v1.begin(), v1.end(), v2.begin(), v2.end(), tr[x].allid.begin());
}
 
int query(int x, int l, int r)
{
	auto &v = tr[x].allid;
	auto iter1 = std::lower_bound(v.begin(), v.end(), l), iter2 = std::upper_bound(v.begin(), v.end(), r);
	if (iter1 == v.end() || iter2 == v.begin()) return 0;
	l = *iter1, r = *-- iter2;
	if (l > r) return 0;
	if (l == r) return l;
	if (tr[x].mp.count({l, r})) return tr[x].mp[{l, r}];
	int sl = query(x << 1, l, r), sr = query(x << 1 | 1, l, r);
	if (!sl || !sr) return sl | sr;
	gt[++ tot] = {sl, sr};
	return tr[x].mp[{l, r}] = tot;
}
 
int main()
{
	std::cin >> n >> Q;
	for (int i = 1; i <= n; ++ i) scanf("%d", &p[i]);
	for (int i = 1; i <= n; ++ i) nw[p[i]] = i;
	build(1, 1, n), tot = n;
	int l, r;
	std::vector<int> ans;
	while (Q --)
	{
		scanf("%d %d", &l, &r);
		ans.push_back(query(1, l, r));
	}
	write(tot, '\n');
	for (int i = n + 1; i <= tot; ++ i) write(gt[i].first, ' ', gt[i].second, '\n');
	for (int &x : ans) write(x, ' ');
	return 0;
}