根号分治 + 入门题目

根号分治解决的问题有这种特点：

1. 可以将问题按照某个界限拆分为两个子问题，通常界限设为 $\sqrt{n}$
2. 对于拆分出来的两个子问题，一部分可以暴力求解，另一部分可以使用算法求解。这样分治的话，可以使得两个子问题的时间复杂度刚好都是 $n\cdot \sqrt{n}$ ，得以解决问题

---

题目：

---

E. Array Queries

题意：

• 给定长度为 $n$ 的序列 $a$。$m$ 次询问。
• 每次询问给出 $p,k$。您要不断地执行操作 $p\leftarrow p+a_p+k$，直到 $p>n$ 为止。询问的答案为操作次数。
• $1\le n,q\le 10^5$，$1\le a_i\le n$，$1\le p,k\le n$。

思路：

对于 $k>\sqrt{n}$ 的询问，暴力即可，枚举的次数不超过 $\sqrt{n}$ 。

对于 $k\le \sqrt{n}$ 的询问，可以预处理 $(p,k)$ 状态需要跳的步数，时空复杂度 $O(n\cdot \sqrt{n})$ 。

AC代码：https://codeforces.com/contest/797/submission/182309787

---

D1. Frequency Problem (Easy Version)

题意：

给定 $a_1,a_2,...,a_n$，求最长的满足区间众数有至少两种的区间长度。如果不存在这样的区间，输出 $0$。

$n\le 2\times 10^5,1\le a_i\le \min (100,n)$

思路：略。详见 题解 。

AC代码：https://codeforces.com/contest/1446/submission/182314629

---

D2. Frequency Problem (Hard Version)

题意：将上一题的 $1\le a_i\le \min (100,n)$ 改为 $1\le a_i\le n$ 。

题解：题解 CF1446D1 【Frequency Problem (Easy Version)】

思路：

对于 $a_i>\sqrt{n}$ 的数字，最多有 $\sqrt{n}$ 种，按照 easy.ver 的思路即可。

对于 $a_i\le \sqrt{n}$ 的数字，枚举出现次数上界，然后双指针找最长子区间。

AC代码：https://codeforces.com/contest/1446/submission/182317190