[COI 2024] CERN

Luogu

IDLGP10749

Time4000ms

Memory512MB

DifficultyP5

2024COI（克罗地亚）

CERN 是一个专注于核研究和粒子物理学的国际机构。CERN 的粒子加速器系统被用于进行高速粒子碰撞实验。我们考虑按序列排列的 $N$ 个粒子。每个粒子由其类型 $v_i$ 定义，$v_i$ 是一个介于 $1$ 和 $N$ 之间的正整数。在最新的研究中，需要进行 $Q$ 次实验。在第 $i$ 次实验中，我们观察序列中从第 $l$ 个到第 $r$ 个的所有粒子（其中 $l < r$）。在观察到的粒子中，我们可以选择任意两个类型不同的粒子并在加速器中进行碰撞，导致两个粒子都被摧毁。我们重复这个碰撞过程，直到观察到的粒子中没有两个类型不同的粒子为止。实验将在所有观察到的粒子都被摧毁或仅剩下同类型的粒子时结束。当然，根据我们碰撞粒子的顺序，最终可能留下各种类型的粒子。由于粒子碰撞成本高昂，你决定只在理论上进行实验。现在，对于每次实验，你感兴趣的是有多少种类型的粒子，使得实验结束时可能剩下该类型的粒子。 ## Input 第一行包含两个正整数 $N$ 和 $Q$，分别表示粒子的数量和实验的次数。第二行包含 $N$ 个数 $v_1, \dots, v_N$，表示粒子的类型。接下来的 $Q$ 行中，每行包含两个正整数 $l$ 和 $r$（$1 \leq l < r \leq N$），表示第 $i$ 次实验中观察到的粒子区间。 ## Output 对于每次实验，在单独的一行中输出可能的结束实验时剩余的粒子类型数量。 [samples] ## Background 题目来源：<https://hsin.hr/hio2024/>。翻译来自 [文心一言](https://yiyan.baidu.com/)。如果有更好的翻译请在讨论区提供。 ## Note **【样例解释】** 在第一个实验中，我们可以使类型为 $3$ 和 $4$ 的粒子相撞，留下两个类型为 $2$ 的粒子。无法最终得到任何其他类型的粒子。在第二个实验中，有可能最终剩下每种类型的一些粒子。在第四和第五个实验中，不论选择哪种碰撞方式，最终都会剩下一些类型为 $4$ 的粒子。 **【数据范围】** 在所有子任务中，$2 \leq N \leq 5\times 10^5$ 且 $1 \leq Q \leq 5\times 10^5$。 - 子任务 1（13 分）：对于每个 $i = 1, \dots, N，v_i \leq 10$。 - 子任务 2（19 分）：每种类型的粒子最多只有两个。 - 子任务 3（17 分）：$N, Q \leq 2\times 10^3$。 - 子任务 4（19 分）：$N, Q \leq 1\times 10^5$。 - 子任务 5（32 分）：没有额外的约束条件。

Samples

Input #1

11 5
2 4 2 3 4 4 3 1 4 4 4
1 4
2 8
6 9
8 10
8 11

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[COI 2024] CERN",
    "description": {
      "content": "CERN 是一个专注于核研究和粒子物理学的国际机构。CERN 的粒子加速器系统被用于进行高速粒子碰撞实验。 我们考虑按序列排列的 $N$ 个粒子。每个粒子由其类型 $v_i$ 定义，$v_i$ 是一个介于 $1$ 和 $N$ 之间的正整数。 在最新的研究中，需要进行 $Q$ 次实验。在第 $i$ 次实验中，我们观察序列中从第 $l$ 个到第 $r$ 个的所有粒子（其中 $l < r$）。在观察",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10749"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "CERN 是一个专注于核研究和粒子物理学的国际机构。CERN 的粒子加速器系统被用于进行高速粒子碰撞实验。\n\n我们考虑按序列排列的 $N$ 个粒子。每个粒子由其类型 $v_i$ 定义，$v_i$ 是一个介于 $1$ 和 $N$ 之间的正整数。\n\n在最新的研究中，需要进行 $Q$ 次实验。在第 $i$ 次实验中，我们观察序列中从第 $l$ 个到第 $r$ 个的所有粒子（其中 $l < r$）。在观察...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments