根号分治
有多种题目类型, 但主要思想就是按是否超过阈值 T 分类。其中大小超过 T 的共有(frac nT)个，但其个数不超过 T ，小于 T 的个数虽多，但其大小较优，因此我们可以根据不同题目的性质设计两种算法，分别适用
例题一： CF1039D You Are Given a Tree
题目大意
有一棵 n 个节点的树
其中一个简单路径的集合被称为 k 合法当且仅当：
树的每个节点至多属于其中一条路径，且每条路径恰好包含 k 个点
对于 k ∈ [1, n]，求出 k 合法路径集合的最多路径数
即：设k合法路径集合为 S ，求最大的 |S|
数据范围
(2 le n le 100000)
解题思路
一般来说根号分治一部分是可以直接暴力做，另一部分利用其他技巧
在此题中，设阈值为 T，k 小于 T 时可以暴力 (Theta(n)) 扫一遍，大于 T 时发现答案的个数不会超过 (frac nT) 个，并且答案具有单调性，我们可以二分查找每个答案控制哪个区间即可，复杂度 (Theta(frac {n^2log_2N}{T}))，平衡复杂度得 (T = sqrt{nlog_2N}) 时最优。
其他优化：递归改成递推会快很多，采用整体二分可以去掉 log
从网上复制下来的整体二分代码
inline void solve(int l, int r, int L, int R) {
if (l > r || L > R) return;
if (L == R) {
for (int i = l; i <= r; i++) ans[i] = L; return;
}
int mid = (l + r) >> 1;
cur = mid; cnt = 0; dfs(1, 0); ans[mid] = cnt;
solve(l, mid - 1, cnt, R); solve(mid + 1, r, L, cnt);
}
完整代码：
int dp[N], d[N], f[N], mx[N], t;
void dfs(int x, int fa) {
d[++t] = x, f[x] = fa;
for (auto y: to[x]) if (y ^ fa) dfs(y, x);
}
#define re register
int get(int k) {
int cnt = 0;
for (re int i = n; i; --i) dp[i] = 1;
for (re int i = n; i ; --i) {
int x = d[i];
if (f[x] && dp[f[x]] && dp[x]) {
if (dp[x] + dp[f[x]] >= k)
cnt++, dp[f[x]] = 0;
else Mx(dp[f[x]], dp[x] + 1);
}
}
return cnt;
}
int ans[N];
int main() {
ios::sync_with_stdio(false);
read(n); int m = sqrt(n * log(n) / log(2));
for (re int i = n - 1, x, y; i; i--)
read(x), read(y), add(x, y);
ans[1] = n, dfs(1, 0);
for (re int i = 2;i <= m; i++) ans[i] = get(i);
for (re int i = m + 1, l, r, t;i <= n; i = r + 1) {
l = i, r = n, t = get(i);
while (l <= r) {
int mid = (l + r) >> 1;
if (get(mid) ^ t) r = mid - 1;
else l = mid + 1;
}
for (re int j = i;j <= r; j++) ans[j] = t;
}
for (re int i = 1;i <= n; i++) cout << ans[i] << endl;
return 0;
}
习题：
例题二：CF587F Duff is Mad
题目大意
给定 (n) 个字符串 (s_{1 dots n})。
- (q) 次询问 (s_{l dots r}) 在 (s_k) 中出现了多少次。
- (n,q,sum_{i=1}^n |s_i| le 10^5)。
解题思路
很容易想到暴力思路,，离线后直接暴力在原 trie 树上走， 拿树状数组维护一下就行
很不巧的是 (sum|s_k|) 并没有保证,，因为一个 k 可以被询问多次，因此我们考虑其他做法
然后我们想如果 (|s_k| le sqrt m) （m 是字符串大小之和），直接暴力做是可行的， 这样复杂度为 (Theta(qlog_q+nsqrt m log_m))， 可以改变阈值获得更优的复杂度， 但这样也可过
如果 (|s_k| ge sqrt m)， 代表着这样的串只有 (sqrt m) 个, 即使对每个串 (Theta(n)) 暴力也可以了, 所以我们将询问挂在 (s_k) 上， 将它的每个前缀节点标记为 1 ， dfs 一遍求子树权值和，从 1 到 n 加入字符串，直接加上 val[end[i]] 就是字符串 i 的贡献
我的 dfs 直接写的暴力跳 fail，结果也过了?!
这题需要对大于小于阈值的两种情况使用两种算法
代码如下:
const int N = 100500;
vector<char> s[N];
char res[N];
int ch[N][26], en[N], dfn[N];
int f[N], cnt, num, T, m, n;
int ne[N], to[N], h[N], tot;
inline void add_e(int x, int y) {
ne[++tot] = h[x], to[h[x] = tot] = y;
}
int add(char *s, int len) {
int p = 0;
for (int i = 1;i <= len; i++) {
int di = s[i] - 'a';
if (!ch[p][di]) ch[p][di] = ++cnt;
p = ch[p][di];
} return p;
}
void build(void) {
queue<int> q;
for (int i = 0;i < 26; i++)
if (ch[0][i]) q.push(ch[0][i]);
while (q.size()) {
int x = q.front(); q.pop();
add_e(f[x], x);
for (int i = 0;i < 26; i++)
if (ch[x][i]) f[ch[x][i]] = ch[f[x]][i], q.push(ch[x][i]);
else ch[x][i] = ch[f[x]][i];
}
}
int siz[N];
void dfs(int x) {
dfn[x] = ++num, siz[x] = 1;
for (int i = h[x]; i; i = ne[i])
dfs(to[i]), siz[x] += siz[to[i]];
}
struct node {
int k, l, num;
bool operator < (const node &i) const {
return l < i.l;
}
};
vector<node> v[N], q;
ll ans[N], d[N], val[N];
void Add(int x, int k) {
for (; x <= num; x += x & -x) d[x] += k;
}
ll Sum(int x) {
ll res = 0;
for (; x ; x -= x & -x) res += d[x];
return res;
}
int main() {
read(n), read(m); T = 250;
for (int i = 1;i <= n; i++) {
scanf ("%s", res + 1);
int t = strlen(res + 1); en[i] = add(res, t);
s[i].push_back('f');
for (int j = 1;j <= t; j++) s[i].push_back(res[j]);
}
build(); dfs(0);
for (int i = 1;i <= m; i++) {
int l, r, k; read(l), read(r), read(k);
if ((int)s[k].size() > T) {
if (l-1) v[k].push_back((node){-1, l-1, i});
v[k].push_back((node){1, r, i});
}
else {
if (l-1) q.push_back((node){-k, l-1, i});
q.push_back((node){k, r, i});
}
}
sort(q.begin(), q.end());
for (int i = 1;i <= n; i++) {
if (!v[i].size()) continue;
sort(v[i].begin(), v[i].end());
memset(val, 0, sizeof(val));
int p = 0;
for (int j = 1;j < (int)s[i].size(); j++) {
p = ch[p][s[i][j]-'a'];
int x = p;
while (x) val[x]++, x = f[x];
}
ll sum = 0, now = 1;
for (auto j: v[i]) {
while (now <= j.l)
sum += val[en[now++]];
ans[j.num] += j.k * sum;
}
}
int now = 1;
for (auto i: q) {
while (now <= i.l) {
int x = en[now];
Add(dfn[x] + siz[x], -1);
Add(dfn[x], 1); now++;
}
int p = 0, f = i.k > 0 ? 1 : -1;
if (i.k < 0) i.k = -i.k;
ll sum = 0;
for (int j = 1;j < (int)s[i.k].size(); j++) {
p = ch[p][s[i.k][j]-'a'];
sum += Sum(dfn[p]);
}
ans[i.num] += f * sum;
}
for (int i = 1;i <= m; i++) printf ("%lld
", ans[i]);
return 0;
}