{"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第一行两个正整数 $n,q$，分别表示电台个数和操作次数。\n\n接下来的 $q$ 行，具体输入格式见题目描述。\n\n## Output\n\n对于每一次 C 操作，输出 `DA` 或者 `NE`。\n\n[samples]\n\n## Note\n\n**【样例 1 解释】**\n\n|C 操作序号|开启电台|是否互相干扰|\n| :----------: | :----------: | :----------: |\n|$1$|$1,2,3$|否|\n|$2$|$1,2,3,6$|是|\n|$3$|$1,3,6$|是|\n\n**【数据规模与约定】**\n\n**本题采用捆绑测试。**\n\n- Subtask 1（10 pts）：$1 \\le n \\le 100$，$1 \\le q \\le 200$。\n- Subtask 2（30 pts）：对于所有的 C 操作，$l=1,r=n$。\n- Subtask 3（70 pts）：无特殊限制。\n\n对于 $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$。\n\n**【来源】[COCI 2021-2022#5](https://hsin.hr/coci/contest5_tasks.pdf) Task 4 Radio。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8327","tags":["2021","COCI（克罗地亚）"],"sample_group":[["6 8\nS 1\nS 2\nS 3\nC 1 6\nS 6\nC 1 6\nS 2\nC 1 6","NE\nDA\nDA"],["11 6\nS 4\nS 10\nC 3 11\nC 2 7\nS 6\nC 2 7","DA\nNE\nDA"],["20 7\nS 10\nS 15\nS 3\nC 10 15\nS 10\nC 3 15\nC 3 10","DA\nDA\nNE"]],"created_at":"2026-03-03 11:09:25"}}