[算法题解] Codeforces round 979 --D. QED's Favorite Permutation

07bit / 2024-11-12 / 原文

题目链接：https://codeforces.com/contest/2030/problem/D

题目：

题解：

Favotite Permutation即每个数满足i=p[i]；此题中，p数组每次询问后保持不变，s根据询问而改变。因此每次需要进行交换的数的位置是相同的，只需要检验s变更后,操作能否满足交换需求与否。故创建需数组need,预处理need，need[i]>0表示p[i]!=i，需要进行交换；创建哈希集合not_ok_pos表示在该位置是交换需求无法满足。
（need数组进行差分处理，因为当需要交换的数中间间隔多个数字时，则要保证左右两个需要的数字及中间数字都能进行交换，即从i->j,need[i]->need[j]都要处理，差分简化操作）
关于s的操作，当s[i]满足以下条件 s[i]->s[i+1] 或者 s[i]<-s[i-1] 或者 s[i]<->s[i+1]），才能交换，但是前二者，只是单向意愿的满足，若将是s[i]->s[i+1]中是s[i]='R'变为'L'指向左边则不能交换，第二个式子同理。
预处理not_ok_pos数组，当最开始输入的操作不能满足需要交换的数的需求时，将该位置添加进哈希表中。
处理询问：输入是s中反转的位置，反转当前s[x]会对左右相邻的数可交换性产生影响，故需要根据左右两边是否有需求进行s[i]反转后的操作检验。
1. need[x-1]>1，需要操作。反转后,若原来当前位不能交换，即s[x-2]<-s[x-1],s[x]->s[x+1],反转后，是s[x-1]<-s[x],可以交换，满足条件，将x-1从not_ok_pos中删去；若原来当前位置能交换，s[x-1]<-s[x],变为，s[x]->s[x+1],不能交换，将x-1添加到not_ok_pos;
  2.与上面同理。
  3.若not_ok_pos不为空，即操作后仍然存在怕p[i]!=i,输出NO；为空，输出YES;

代码如下：

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

#define fi first
#define se second
#define ll long long
#define pii pair<int, int>

bool ok(char l, char r) {
    return l == 'R' || r == 'L';
}

int a[N], q, n, need[N];
char s[N];

void solve() {
    set<int> not_ok_pos;
    vector<pii> v;
    for (int i = 1; i <= n; i++) need[i] = 0;

    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (i == a[i]) continue;
        int u = i, v = a[i];
        if (u > v) swap(u, v);
        need[u]++, need[v]--; // 差分
    }

    for (int i = 1; i <= n; i++) need[i] += need[i - 1];

    for (int i = 1; i <= n; i++) cin >> s[i];

    for (int i = 1; i < n; i++) {
        if (need[i] && !ok(s[i], s[i + 1])) not_ok_pos.insert(i);
    }

    while (q--) {
        int x;
        cin >> x;

        if (need[x - 1]) {
            if (!ok(s[x - 1], s[x])) not_ok_pos.erase(x - 1);
            if (ok(s[x - 1], s[x]) && s[x - 1] == 'L') not_ok_pos.insert(x - 1);
        }

        if (need[x]) {
            if (!ok(s[x], s[x + 1])) not_ok_pos.erase(x);
            if (ok(s[x], s[x + 1]) && s[x + 1] == 'R') not_ok_pos.insert(x);
        }

        if (s[x] == 'L')
            s[x] = 'R';
        else
            s[x] = 'L';

        if (not_ok_pos.size()) {
            cout << "NO" << endl;
        } else {
            cout << "YES" << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while (t--) { solve(); }
    return 0;
}