自动搬运

查看原文

来自洛谷，原作者为

	SunSkydp 开

搬运于2025-08-24 22:51:34，当前版本为作者最后更新于2023-10-16 16:46:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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;
}