[COCI 2021/2022 #5] Radio

Luogu

IDLGP8327

Time1500ms

Memory512MB

DifficultyP6

2021COCI（克罗地亚）

克罗地亚有 $n$ 个初始状态下关闭的电台。当同时开启两个电台 $i,j$ 且 $i,j$ 不互质时，它们会互相干扰。你需要写一个支持下列操作的程序： 1. `S x`：将电台的状态取反，即将原来开启的电台关闭，将原来关闭的开启。 2. `C l r`：检查在 $[l,r]$ 内是否存在互相干扰的现象。如果存在，输出 `DA`，否则输出 `NE`。 ## Input 第一行两个正整数 $n,q$，分别表示电台个数和操作次数。接下来的 $q$ 行，具体输入格式见题目描述。 ## Output 对于每一次 C 操作，输出 `DA` 或者 `NE`。 [samples] ## Note **【样例 1 解释】** |C 操作序号|开启电台|是否互相干扰| | :----------: | :----------: | :----------: | |$1$|$1,2,3$|否| |$2$|$1,2,3,6$|是| |$3$|$1,3,6$|是| **【数据规模与约定】** **本题采用捆绑测试。** - Subtask 1（10 pts）：$1 \le n \le 100$，$1 \le q \le 200$。 - Subtask 2（30 pts）：对于所有的 C 操作，$l=1,r=n$。 - Subtask 3（70 pts）：无特殊限制。对于 $100\%$ 的数据，$1 \le n \le 10^6$，$1 \le q \le 2 \times 10^5$，$1 \le x \le n$，$1 \le l \le r \le n$。 **【来源】[COCI 2021-2022#5](https://hsin.hr/coci/contest5_tasks.pdf) Task 4 Radio。**

Samples

Input #1

Output #1

NE
DA
DA

Input #2

Output #2

DA
NE
DA

Input #3

Output #3

DA
DA
NE

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2021/2022 #5] Radio",
    "description": {
      "content": "克罗地亚有 $n$ 个初始状态下关闭的电台。当同时开启两个电台 $i,j$ 且 $i,j$ 不互质时，它们会互相干扰。 你需要写一个支持下列操作的程序： 1. `S x`：将电台的状态取反，即将原来开启的电台关闭，将原来关闭的开启。 2. `C l r`：检查在 $[l,r]$ 内是否存在互相干扰的现象。如果存在，输出 `DA`，否则输出 `NE`。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8327"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "克罗地亚有 $n$ 个初始状态下关闭的电台。当同时开启两个电台 $i,j$ 且 $i,j$ 不互质时，它们会互相干扰。\n\n你需要写一个支持下列操作的程序：\n\n1. `S x`：将电台的状态取反，即将原来开启的电台关闭，将原来关闭的开启。\n2. `C l r`：检查在 $[l,r]$ 内是否存在互相干扰的现象。如果存在，输出 `DA`，否则输出 `NE`。\n\n## Input\n\n第一行两个正整数 $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments