[COCI 2022/2023 #3] Dirigent

Luogu

IDLGP9757

Time1000ms

Memory512MB

DifficultyP3

2022COCI（克罗地亚）

信息学冬令营以一场传统舞蹈结营。一共有 $n$ 名学生参与。他们每个人都有分别有一个 $1\sim n$ 之间的编号。一开始，指挥者 Kreso 要求学生们围成一个圈，使得每个学生都与另外两个学生拉着手。 Alenka 想知道是否有可能通过将且仅将一对相邻同学分开手，使得这样形成的同学序列按照编号排序。例如，如果他们的顺序是 `3 4 1 2`，那么圈可以从 `4` `1` 两个同学间断开；但是如果顺序是 `2 1 4 3`，那么没有一种合理的方式。在这一晚，Kreso 准备下达 $q$ 条指令。在每条指令中，他会要求两个学生交换位置。在每一次交换之后你需要帮助 Alenka 回答他的问题。 ## Input 第一行包含两个整数 $n,q$，表示学生的数量和交换数。第二行包含 $n$ 个整数 $a_i$，描述第 $i$ 个位置的学生编号。在接下来的 $q$ 行中，每行两个整数 $x_i,y_i$，描述 Kreso 的第 $i$ 条指令，即标号 $x_i$ 的学生和标号 $y_i$ 的学生交换位置。 ## Output 共 $q$ 行。在第 $i$ 行输出在第 $i$ 次交换后 Alenka 的问题的答案。如果答案是肯定的，输出 `DA`，否则输出 `NE`。 [samples] ## Note **【样例解释 #2】** ![](https://cdn.luogu.com.cn/upload/image_hosting/382d6t5r.png) **【数据范围】** | 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $15$ | $n,q \leq 500$ | | $2$ | $20$ | $n,q \leq 5000$ | | $3$ | $35$ | 无特殊性质 | 对于 $100\%$ 的数据，满足 $1\leq n,q \leq 3\times10^5,1\le a_i\le n, 1\le x_i,y_i\le n,x_i\neq y_i$。本题满分 $70$ 分。

Samples

Input #1

Output #1

NE
DA

Input #2

Output #2

NE
DA

Input #3

6 5
2 1 5 6 3 4
3 1
3 4
3 2
4 5
5 4

Output #3

NE
NE
DA
NE
DA

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2022/2023 #3] Dirigent",
    "description": {
      "content": "信息学冬令营以一场传统舞蹈结营。一共有 $n$ 名学生参与。他们每个人都有分别有一个 $1\\sim n$ 之间的编号。 一开始，指挥者 Kreso 要求学生们围成一个圈，使得每个学生都与另外两个学生拉着手。 Alenka 想知道是否有可能通过将且仅将一对相邻同学分开手，使得这样形成的同学序列按照编号排序。例如，如果他们的顺序是 `3 4 1 2`，那么圈可以从 `4` `1` 两个同学间断开；",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9757"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "信息学冬令营以一场传统舞蹈结营。一共有 $n$ 名学生参与。他们每个人都有分别有一个 $1\\sim n$ 之间的编号。\n\n一开始，指挥者 Kreso 要求学生们围成一个圈，使得每个学生都与另外两个学生拉着手。\n\nAlenka 想知道是否有可能通过将且仅将一对相邻同学分开手，使得这样形成的同学序列按照编号排序。例如，如果他们的顺序是 `3 4 1 2`，那么圈可以从 `4` `1` 两个同学间断开；...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments