CF1514D Cut and Stick

小 Ehab 有一张 Cut and Stick 纸条，上面写着一个长度为 $n$ 的数组 $a$。他打算拿起一把剪刀，对其进行如下操作： - 选择一个区间 $(l, r)$，剪下区间内的所有元素 $a_l$、$a_{l+1}$、…、$a_r$； - 将其中的一些元素按照它们在数组中的原有顺序粘贴在一起； - 最终得到若干个片段，每个片段包含部分元素，且每个元素都属于某个片段。 更正式地说，他将序列 $a_l$、$a_{l+1}$、…、$a_r$ 分割成若干个子序列。他认为一种分割是美丽的，当且仅当对于每个片段（子序列），如果其长度为 $x$，则没有任何一个值在该片段中出现次数严格大于 $\lceil \frac{x}{2} \rceil$。 他还没有选择区间，所以他想知道：对于 $q$ 个区间 $(l, r)$，最少需要将区间 $a_l$、$a_{l+1}$、…、$a_r$ 分成多少个子序列，才能使分割是美丽的。 如果序列 $b$ 是数组 $a$ 的一个子序列，表示 $b$ 可以通过从 $a$ 中删除一些（可能为零个）元素得到。注意，子序列不要求连续。

第一行包含两个整数 $n$ 和 $q$（$1 \le n, q \le 3 \times 10^5$）——数组 $a$ 的长度和询问的个数。 第二行包含 $n$ 个整数 $a_1$、$a_2$、…、$a_n$（$1 \le a_i \le n$）——数组 $a$ 的元素。 接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$）——表示一次询问的区间。

对于每个询问，输出将该区间分割成美丽的子序列所需的最少子序列数。可以证明总是存在这样的分割。

对于第一个询问，你可以直接将整个数组作为一个子序列，因为其长度为 $6$，且没有任何值出现超过 $3$ 次。 对于第二个询问，区间内的元素为 $[3,2,3,3]$。你不能将它们全部放在一个子序列中，因为其长度为 $4$，而 $3$ 出现了超过 $2$ 次。然而，你可以将其分为两个子序列：$[3]$ 和 $[2,3,3]$。 由 ChatGPT 4.1 翻译