P11146 Strange Train Game 题解

幸存者 · 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