题解：CF1697C awoo's Favorite Problem

xz001 · 2025-07-05 09:42:19 · 题解

首先我们发现 b 可以在连续 a 构成的水流中向前流动，c 可以在连续 b 构成的水流中向前流动（其他情况的向后流动相当于后面的向前流动），所以我们维护三个树状数组，分别表示 s 每个位置上的三种字母数量，然后每次遇到 s_i=b 且 t_i=c 就找到后面最近的 b 水流中的 c，遇到 s_i=a 且 t_i=b 就找到后面最近的 a 水流中的 b，交换更改信息即可，时间复杂度 O(n\log^2n)，最慢的题解，思路比已有题解简单好写。

代码：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e6 + 5;

int q, n, tt[3][N];

string s, t;

void modify (int at, int x, int k) {
    while (x <= n) {
        tt[at][x] += k;
        x += x & -x;
    }
    return;
}

int query (int at, int x) {
    int ans = 0;
    while (x) {
        ans += tt[at][x];
        x ^= x & -x;
    }
    return ans;
}

signed main() {
    cin >> q;
    while (q -- ) {
        cin >> n >> s >> t;
        s = " " + s, t = " " + t;
        for (int i = 1; i <= n; ++ i ) {
            tt[0][i] = tt[1][i] = tt[2][i] = 0;
        }
        for (int i = 1; i <= n; ++ i ) {
            if (s[i] == 'a') modify (0, i, 1);
            if (s[i] == 'b') modify (1, i, 1);
            if (s[i] == 'c') modify (2, i, 1); 
        }
        bool is = true;
        for (int i = 1; i <= n; ++ i ) { 
            if (s[i] != t[i]) { //cout << i << endl;
                if (t[i] == 'c' && s[i] == 'b') {
                    int l = i, r = n, res = 0;
                    while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (query (2, mid) - query (2, i - 1)) {
                            res = mid;
                            r = mid - 1;
                        } else {
                            l = mid + 1;
                        }
                    }
                    if (!res || query (1, res - 1) - query (1, i - 1) != res - i) {
                        is = false;
                        break;
                    }
                    swap(s[i], s[res]);
                    modify (2, res, -1);
                    modify (1, res, 1);
                } else if (t[i] == 'b' && s[i] == 'a') {
                    int l = i, r = n, res = 0;
                    while (l <= r) {
                        int mid = (l + r) >> 1;
                        if (query (1, mid) - query (1, i - 1)) {
                            res = mid;
                            r = mid - 1;
                        } else {
                            l = mid + 1;
                        }
                    }
                    if (!res || query (0, res - 1) - query (0, i - 1) != res - i) {
                        is = false;
                        break;
                    }
                    swap(s[i], s[res]);//cout << i << ' ' << res << endl;
                    modify (1, res, -1);
                    modify (0, res, 1);
                } else is = false;
            } 
        }
        if (is) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}