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

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

题目：

E. Array Queries

题意：

• 给定长度为 nnn 的序列 aaa。mmm 次询问。
• 每次询问给出 p,kp,kp,k。您要不断地执行操作 p←p+ap+kp\gets p+a_p+kp←p+ap​+k，直到 p>np>np>n 为止。询问的答案为操作次数。
• 1≤n,q≤1051\le n,q\le 10^51≤n,q≤105，1≤ai≤n1\le a_i\le n1≤ai​≤n，1≤p,k≤n1\le p,k\le n1≤p,k≤n。

思路：

对于 k>nk> \sqrt nk>n​ 的询问，暴力即可，枚举的次数不超过 n\sqrt nn​ 。

对于 k≤nk\leq \sqrt nk≤n​ 的询问，可以预处理 (p,k)(p,k)(p,k) 状态需要跳的步数，时空复杂度 O(n⋅n)O(n\cdot \sqrt n)O(n⋅n​) 。

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

D1. Frequency Problem (Easy Version)

题意：

给定 a1,a2,...,ana_1,a_2,...,a_na1​,a2​,...,an​，求最长的满足区间众数有至少两种的区间长度。如果不存在这样的区间，输出 000。

n≤2×105,1≤ai≤min⁡(100,n)n\leq 2\times 10^5,1\leq a_i\leq \min(100,n)n≤2×105,1≤ai​≤min(100,n)

思路：略。详见 题解 。

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

D2. Frequency Problem (Hard Version)

题意：将上一题的 1≤ai≤min⁡(100,n)1\leq a_i\leq \min(100,n)1≤ai​≤min(100,n) 改为 1≤ai≤n1\leq a_i\leq n1≤ai​≤n 。

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

思路：

对于 ai>na_i> \sqrt nai​>n​ 的数字，最多有 n\sqrt nn​ 种，按照 easy.ver 的思路即可。

对于 ai≤na_i\leq \sqrt nai​≤n​ 的数字，枚举出现次数上界，然后找最长子区间。

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