P9757 [COCI2022-2023#3] Dirigent 题解

· · 题解

subtask#1 和 subtask#2 都是暴力好吧，直接讲正解了。

我们将每对左右相邻的两位同学组合为一个 pair，即对于任意的 1 \leq i \leq n，a_i 和 a_{(i+1)\mod n} 可以组成一个 pair。

我们定义当一个 pair 的第一关键字小于第二关键字时，这个 pair 为“好”的 pair，反之为“坏”的。题目的条件为环从某一处断开能够形成一个单调上升的序列，那么当所有的 n 个 pair 中，有且仅有 1 个 pair 是“坏”的，就可以满足题意了。

妙啊！那每次 query 的时候，不就只要修改 4 个 pair 吗？受到影响的 pair 有：x 作为第一关键字所在 pair、y 作为第一关键字所在 pair、x 作为第二关键字所在 pair、y 作为第二关键字所在 pair。

这里我还添加了 id1 和 id2 数组（具体见代码），id1_i 表示第一关键字为 i 的 pair 的编号，id2_i 表示第二关键字为 i 的 pair 的编号。

接下来是代码啦，不懂的评论里提问，写的不好的地方请在评论里指出。

#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
int n, q, a[N], bad;
pair<int, int> stu[N];
int id1[N], id2[N];
bool is_bad(pair<int, int> p) {return p.first > p.second; }
int change(int a, int b, int c, int d) {
    return is_bad(stu[a]) + (b != a ? is_bad(stu[b]) : 0)
    + ((c != b && c != a) ? is_bad(stu[c]) : 0) 
    + ((d != c && d != b && d != a) ? is_bad(stu[d]) : 0);
}
int main() {
    scanf("%d %d", &n, &q);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++) {
        if(i == n) stu[i] = make_pair(a[n], a[1]), id1[a[n]] = id2[a[1]] = i;
        else stu[i] = make_pair(a[i], a[i + 1]), id1[a[i]] = id2[a[i + 1]] = i;
        if(is_bad(stu[i])) bad++;
    }
    while(q--) {
        int x, y; scanf("%d %d", &x, &y);
        int a = id1[x], b = id2[x], c = id1[y], d = id2[y];
        bad -= change(a, b, c, d);
        stu[id1[x]].first = stu[id2[x]].second = y;
        stu[id1[y]].first = stu[id2[y]].second = x;
        id1[x] = c; id2[x] = d; id1[y] = a; id2[y] = b;
        bad += change(a, b, c, d);
        if(bad == 1) puts("DA");
        else puts("NE");
    }
    return 0;
}