根号分治

模型

大概就是，对于一类问题，可以用 $O(n^2)$ 预处理并 $O(1)$ 查询，或者用 $O(n)$ 处理每个询问，复杂度都是 $O(n^2)$ 数量级

此时可以通过预处理前 $\sqrt{N}$ 的部分，并对 $\sqrt{N}\sim N$ 的部分暴力以达到 $O(N\sqrt{N})$ 的复杂度

这跟筛法的思路相近

例题

P5901 [IOI2009]regions

有 $n$ 位委员，第 $1$ 个资历最高，委员所属的地区为 $1\sim R$ ，除第一个以外的所有委员都有一个直接导师，任何直接导师的资历高于其指导的委员，给定两个地区 $r_1,r_2$ ，要求回答有多少对委员 $e_1,e_2$ 满足 $e_1\in r_1,e_2\in r_2$ ，且 $e_1$ 是 $e_2$ 的导师

这个题有一个很好的启示：针对询问地区的大小设计不同的算法

不妨设 $r_1$ 中的点有 $A$ 个 $x_1,x_2,…,x_A$ ，$r_2$ 中的点有 $B$ 个 $y_1,y_2,…,y_B$

• 如果 $A$ 不大而 $B$ 很大

  那么可以接受扫描 $A$ 而不能扫描 $B$

  考虑 $dfs$ 序，$A$ 中每个节点的子树在 $dfs$ 序中都对应一段区间 $[l_A,r_A]$ ，而若 $y$ 是 $x$ 的子节点当且仅当 $l_x\leq l_y \And r_x\geq r_y \Leftrightarrow l_x\leq l_y \And r_x\geq l_y$

  那么枚举每个以 $x$ 为根的子树，$dfs$ 序按 $l_i$ 排序，二分

  用 $lower_bound$ 容易实现，复杂度 $O(A\log B)$

• $A$ 很大而 $B$ 不大

  上面启示我们应该设计一个 $O(B\log A)$ 的算法

  也就是找到多少区间 $[l_x,r_x]$ 包含 $l_y$

  仍可以用 $\text{lower_bound}$ 实现

• $A$ 很大且 $B$ 很大

  此时只能有无法优化的 $O(A+B)$ ，但考虑一个涉及很多点的询问不会出现多次，对于重复出现记忆化即可

  具体的，当有 $y$ 满足 $l_y\in[l_x,r_y]$ 时表明前面的 $l_x,r_x$ 已经没用了，那么考虑尺取，对于每一个 $y$ ，找在当前 $x$ 之后的 $x$ 以累加答案

  嗯，玄学证明

而对于不同复杂度的算法选取，论文给出的答案是 $lim=\sqrt{N\log N}$ ，但这里使用动态分析复杂度

开 $O(2)$ 才苟过的屑代码

const int N=26100;
const int M=2e5+100;
const int INF=19260817;
int tot,head[M],ver[M<<1],Next[M<<1];
vector<int> dfn_left[N],num[N];
vector<PII> range[N];
map<PII,int> ans;
int Size[M],re_dfn[M],area[M],dfn_cnt;
int n,r,q,x,y;

inline int read(){ rei ans=0; char ch=getchar(); while(ch<'0' || ch>'9') ch=getchar(); while(ch>='0' && ch<='9'){ ans=(ans<<1)+(ans<<3)+(ch^48); ch=getchar();} return ans;}
inline void add(int u,int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}

void dfs(int x,int fa=1){
    Size[x]=1; re_dfn[++dfn_cnt]=x; dfn_left[ area[x] ].push_back(dfn_cnt);
    for(rei i=head[x],y;i;i=Next[i]){
        y=ver[i]; if(y==fa) continue;
        dfs(y,x);
        Size[x]+=Size[y];
    }
}

inline void solve1(){//O(A\log B)
    rei res=0;
    for(rei i=0,SS=dfn_left[x].size();i<SS;++i){
        rei l=dfn_left[x][i],r=l+Size[ re_dfn[l] ]-1;
        l=lower_bound(dfn_left[y].begin(),dfn_left[y].end(),l)-dfn_left[y].begin();
        r=upper_bound(dfn_left[y].begin(),dfn_left[y].end(),r)-dfn_left[y].begin();
        res+=r-l;
    }
    printf("%d\n",ans[ mk(x,y) ]=res);
}

inline void solve2(){//B\log A
    rei res=0;
    for(rei i=0,SS=dfn_left[y].size();i<SS;++i){
        rei tmp=lower_bound(range[x].begin(),range[x].end(),mk(dfn_left[y][i],INF))-range[x].begin()-1;
        if(tmp>=0) res+=num[x][tmp];
    }
    printf("%d\n",ans[ mk(x,y) ]=res);
}

inline void solve3(){//O(A+B)
    rei cntx=0,cnty=dfn_cnt=0,res=0,added=0;
    while(cntx!=range[x].size() || cnty!=dfn_left[y].size()){//对每一对xy，将包含以y为根的子树的以x为根的子树的数量叠加
        if(cntx==range[x].size()) ++cnty,res+=added;
        else if(cnty==dfn_left[y].size()) break;
        else if(range[x][cntx].first<=dfn_left[y][cnty]) added+=range[x][cntx++].second;
        else ++cnty,res+=added;
    }
    printf("%d\n",ans[ mk(x,y) ]=res);
}

int main(){
    n=read(),r=read(),q=read();
    for(rei i=1;i<=n;++i){
        if(i>1){
            rei fa=read();
            add(fa,i);
        }
        area[i]=read();
    }
    dfs(1);
    for(rei i=1;i<=r;++i){
        for(rei j=0,SS=dfn_left[i].size();j<SS;++j){
            range[i].push_back(mk(dfn_left[i][j],1));
            range[i].push_back(mk(dfn_left[i][j]+Size[ re_dfn[ dfn_left[i][j] ] ],-1));
        }
        sort(range[i].begin(),range[i].end());
        sort(dfn_left[i].begin(),dfn_left[i].end());
        rei added=0;
        for(rei j=0,SS=range[i].size();j<SS;++j) num[i].push_back(added+=range[i][j].second);
    }
    while(q--){
        x=read(),y=read();
        if(ans.count(mk(x,y))) printf("%d\n",ans[ mk(x,y) ]);
        else{
            rei O1=dfn_left[x].size()*log2(dfn_left[y].size());
            rei O2=dfn_left[y].size()*log2(range[x].size());
            rei O3=range[x].size()+dfn_left[y].size();
            rei MIN=min(O1,min(O2,O3));
            if(MIN==O1) solve1();
            else if(MIN==O2) solve2();
            else solve3();
        }
    }
    getchar(),getchar();
    return 0;
}

CF1039D You Are Given a Tree

$n$ 个节点的数，其中一个简单路径的集合被称为 $k合法$ 当且仅当树的每个节点至多属于其中一条路径且每条路径恰好包含 $k$ 个点 $\qquad$ 对于 $k\in[1,n]$ 求 $k合法$ 路径集合的最多路径数，即，设 $k合法$路径集合为 $S$ ，求 $\max|S|$

显然能对于每个 $k$ ，在 $O(n)$ 内贪心出最长链

可以发现，随着 $k$ 的增大答案变小，在 $k>\sqrt{n}$ 的情况下，答案取值至多有 $\sqrt{n}$ 种

那么，对于 $k\sqrt{n}$ 的部分，暴力即可

剩下的部分二分求相同的值，至多 $O(\log n)$

可以再考虑分治的优化：设分治点 $T$ ，有 $O(nT+\frac{n^2\log n}{T})$

考虑两项相乘为定值，那么当两者相等，即 $T=\sqrt{n\log n}$ 时，有最优复杂度

#include <bits/stdc++.h>
#define rei register int
using namespace std;

const int N=1e5+100;
int head[N],Next[N<<1],ver[N<<1],tot;
int n,p,fa[N],dfn[N],cnt,ans[N],f[N];

inline void add(int u,int v){ ver[++tot]=v; Next[tot]=head[u],head[u]=tot;}

void dfs(int x,int fath){
    fa[x]=fath;
    for(rei i=head[x],y;i;i=Next[i]){
        y=ver[i]; if(y==fath) continue;
        dfs(y,x);
    }
    dfn[++cnt]=x;
}

inline int solve(int k){
    rei res=0;
    for(rei i=1;i<=n;++i) f[i]=1;
    for(rei i=1;i<=n;++i){
        rei x=dfn[i],fath=fa[x];
        if(fath && f[x]!=-1 && f[fath]!=-1){
            f[x]+f[fath]>=k ? (++res,f[fath]=-1) : (f[fath]=max(f[fath],f[x]+1));
        }
    }
    return res;
}

int main(){
    scanf("%d",&n); p=sqrt(n*log2(n));
    for(rei i=1,u,v;i<n;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u);
    dfs(1,0);
    ans[1]=n; for(rei i=2;i<=p;++i) ans[i]=solve(i);
    for(rei i=p+1;i<=n;++i){
        rei tmp=solve(i);
        rei l=i,r=n,pos=i;
        while(l<r-1){
            rei mid=l+r>>1;
            solve(mid)==tmp ? (l=mid,pos=max(pos,mid)) : r=mid;
        }
        for(;i<=pos;++i) ans[i]=tmp;//类似数论分块
        --i;
    }
    for(rei i=1;i<=n;++i) printf("%d\n",ans[i]);
    getchar(),getchar();
    return 0;
}