自动搬运

查看原文

来自洛谷，原作者为

	幸存者 当生命意识到宇宙奥秘的存在时，距它最终解开这个奥秘只有一步之遥了。

搬运于2025-08-24 23:04:39，当前版本为作者最后更新于2024-10-02 21:13:24，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

自认为非常好写的做法，凭借这个拿到了 16min 一血。

考虑依次确定每一位，对于第 $i$ 位：

• 如果 $a_i=b_i$，这一位没有影响，可以直接把左端点为 $i$ 的区间左端点改成 $i+1$。

• 如果 $a_i=1,b_i=0$，那么一定选偶数个左端点为 $i$ 的区间，不妨设左端点为 $i$ 的区间中右端点最小的为 $[i,x]$。所以所选的偶数个区间都包含 $[i,x]$，恰好抵消掉了，于是可以直接删掉 $[i,x]$，把剩余的左端点为 $i$ 的区间左端点改成 $x+1$。

• 如果 $a_i=0,b_i=1$，那么一定选奇数个左端点为 $i$ 的区间，不妨设左端点为 $i$ 的区间中右端点最小的为 $[i,x]$。本质上和上面是一样的，只需要类似差分把 $[i,x]$ 区间内打一个交换标记就可以了。

简单思考一下，你会发现这个东西完全可以用 set 维护每个左端点对应的右端点构成的集合，启发式合并即可。

时间复杂度 $O(n\log^2n)$，但代码真的很短。

// superyijin AK IOI
// wangsiyuanZP AK IOI
#include <bits/stdc++.h>
#define int long long
using namespace std;
set<int> s[200010];
int p[200010];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	string a, b;
	cin >> n >> m >> a >> b;
	for (int i = 1; i <= m; i++)
	{
		int l, r;
		cin >> l >> r;
		s[l].insert(r);
	}
	a = " " + a, b = " " + b;
	int now = 0;
	for (int i = 1; i <= n; i++)
	{
		now ^= p[i];
		if (now) swap(a[i], b[i]);
		if (a[i] == b[i])
		{
			cout << a[i];
			if (s[i].count(i)) s[i].erase(i);
			if (s[i].size() > s[i + 1].size()) swap(s[i], s[i + 1]);
			s[i + 1].insert(s[i].begin(), s[i].end());
		}
		else
		{
			if (s[i].empty()) cout << a[i];
			else
			{
				cout << "1";
				int x = *s[i].begin();
				s[i].erase(x);
				if (s[i].size() > s[x + 1].size()) swap(s[i], s[x + 1]);
				s[x + 1].insert(s[i].begin(), s[i].end());
				if (b[i] == '1') now ^= 1, p[x + 1] ^= 1;
			}
		}
	}
	cout << endl;
	return 0;
}
// superyijin AK IOI
// wangsiyuanZP AK IOI