鉴于本人能力有限，导致评论系统有些问题

所以如果您想在博客下评论，而登录github账号失败的话，请在 这篇文章 下的评论去登录，即可解决

根号分治，是暴力美学的集大成体现。与其说是一种算法，我们不如称它为一个常用的trick。

首先，我们引入一道入门题目 CF1207F Remainder Problem：

给你一个长度为 $5\times10^5$ 的序列，初值为 $0$ ，你要完成 $q$ 次操作，操作有如下两种：

1. 1 x y: 将下标为 $x$ 的位置的值加上 $y$。
2. 2 x y: 询问所有下标模 $x$ 的结果为 $y$ 的位置的值之和。

1.CF559E Gerald and Path

题目大意：

有 $n$ 条线段，每条线段给定其中一端的位置及长度，求所有线段覆盖的最大长度。

$n \le 100$

难度：Normal，*3000

[ARC048D] たこ焼き屋とQ人の高橋君

题目大意：

给你一棵有 $n$ ($1 \le n \le 10^5$) 个节点的树，其中一些节点是特殊节点，相邻两个点的距离为 $1$。

有 $q$ ($1 \le q \le 10^5$) 次询问，每次给你两个点 $u,v$，你需要求出从 $u$ 走到 $v$ 的最小时间。

一开始，你的速度是每 $2$ 个时间单位走 $1$ 个距离单位。假设在某一时刻你到了一个特殊节点，那么你的速度就会变为 $1$ 个时间单位走 $1$ 个距离单位，这次询问内有效。

题目意思很清楚不用说。

看到每个点都有颜色，然后询问和颜色的种类有关，时限开了很【】的 8s，就可以往根号分治方面想了。

按照常理，我们钦定一个 $B$，所有颜色为 $i$ 的点的集合为 $col_i$。

不定期更新的重型板子库

link

题目大意：

定义一个好集合 $T$：

• 所有元素均为字符串

• $T$ 中不包含两个串 $p,q$，满足 $p$ 是 $q$ 的后缀

先给你一个长度为 $n$ 的字符串$s$，和一个长度为 $n$ 的数组 $v$。

题目有一个很强的提示是“无论怎么走都要能判断出来”，这启示我们可能有很多道路的长度都是相同的。

然后，我们可以这么设计：

• 当 $i$ 固定时，所有 $a_{i,j}$ 到 $a_{i+1,j}$ 的路的长度均相同。

• 当 $j$ 固定时，所有 $a_{i,j}$ 到 $a_{i,j+1}$ 的路的长度均相同。

栈，pair，队列，分数类，vector