根号分治 + 入门题目

根号分治 + 入门题目"/>

根号分治 + 入门题目

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

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

题目：

E. Array Queries

题意：

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

思路：

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

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

AC代码：

D1. Frequency Problem (Easy Version)

题意：

给定 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1​,a2​,...,an​，求最长的满足区间众数有至少两种的区间长度。如果不存在这样的区间，输出 0 0 0。

n ≤ 2 × 1 0 5 , 1 ≤ a i ≤ 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代码：

D2. Frequency Problem (Hard Version)

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

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

思路：

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

对于 a i ≤ n a_i\leq \sqrt n ai​≤n ​ 的数字，枚举出现次数上界，然后双指针找最长子区间。

AC代码：