1. 介绍与引入

没有前言，懒得写了。

根号分治，本质是平衡规划思想（大纲 9 级），在预处理和询问复杂度中寻找平衡，我们通常用根号作为问题规模的分界线。我们确定一个界限 $B$ ，小于 $B$ 的暴力预处理，大于的回答一次时间只需要 $\dfrac{n}{B}\le \sqrt{n}$ ，那么整个题目就可以做到 $O(n \sqrt{n})$ 。

根号平衡思想，是平衡规划思想中重要的内容，例如空间平衡，时间平衡，根号滚动数组，都可以用这种思想。

我们以一道例题引入：CF797E Array Queries

这种操作我们发现没有什么很好的性质来维护，因为 $a_{p}$ 和变化的 $p$ 是有关的。这两个关系是相互制约的，如果我们只关注一个肯定是不行的。怎么办？

首先我们先想暴力，我们有两种想法：

预处理所有 $p,k$ 的答案。
暴力模拟。

第一个虽然可以 $O(1)$ 回答但是预处理时间空间复杂度 $O(nk)$ 无法承受，而暴力算法时间复杂度一次是 $O(\dfrac{n}{k})$ ，是无法承受的。

我们怎么平衡这一算法呢，通过基本不等式 $k+\dfrac{n}{k}\ge 2\sqrt{b\times \dfrac{n}{k}}=2\sqrt{n}$ ，当 $k=\sqrt{n}$ 是取等号。也就是我们当 $k\le \sqrt{n}$ ，我们可以使用预处理的答案，空间是 $O(n\sqrt{n})$ ，而 $k>\sqrt{n}$ 的时候我们暴力模拟即可。故时间空间复杂度为 $O(n\sqrt{n})$ 。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e5+15,MB=300;
int n,m,a[MN],f[MB+15][MN];

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=MB;i++){
        for(int j=n;j>=1;j--){
            f[i][j]=(j+a[j]+i>n)?1:f[i][j+a[j]+i]+1;
        }
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        int p,k,ans=0;
        cin>>p>>k;
        if(k>=MB){
            while(p<=n){
                ans++;
                p+=a[p]+k;
            }
        }else ans=f[k][p];
        cout<<ans<<'\n';
    }
    return 0;
}

我们简单回顾一下这道题，我们通过将两种看似暴力的算法结合起来，形成了一个时间复杂度为 $O(n\sqrt{n})$ 的高效的算法，相互制约的关系我们很难用常规的数据结构进行处理，因为只关心一个的话另一个就会制约你的复杂度。这个时候我们利用平衡规划思想，我们通过制约关系设计出两种算法： $O(nk)$ 与 $O(\dfrac{n^2}{k})$ 的算法，但是我们通过基本不等式算出分界点，通过这个分界点来进行所谓的 “分治”，数据小的跑预处理，大的进行暴力。

这一类思想，就是根号分治的思想，平衡规划。而一般制约关系，或同时涉及两个集合的关系，如果没有特殊性质，基本不能 $\text{polylog}$ 去做，但是我们通过根号分治就可以做。

接下来我们来看几道例题：

2. 例题

CF1039D You Are Given a Tree

先考虑 $O(n^2)$ 的情况下怎么做，也就是说我们枚举 $k$ ，让后一次查询必须是 $O(n)$ 。有一个想法就是暴力贪心，从叶子向根合并，搜到长为 $k$ 的链直接取，证明考虑反证法即可。

让后考虑如何优化，由样例手摸不难发现几个特性：

答案随 $k$ 的增大单调不升。
答案不超过 $\lfloor \dfrac{n}{k} \rfloor$ 。

答案不超过 $\lfloor \dfrac{n}{k} \rfloor$ ？那么我们能不能从这里下手呢？由基本不等式可以得到答案不超过 $2\sqrt{n}$ ，不难想到 $2\sqrt{n}< n$ ，那么也就是说答案是重复的，进一步推广，当 $k>\sqrt{n}$ 的时候答案取值是很少的，而 $k\le \sqrt{n}$ 的答案取值是较多的。哎，一会多，一会少，平衡规划？出动！我们对 $k\le \sqrt{n}$ 直接做是 $O(n\sqrt{n})$ 。考虑 $k>\sqrt{n}$ 的答案是连续是连续的一段，并且答案具有优秀的单调不升的特性，我们可以通过二分找出下一个答案取值的区间，我们只需要跑 $O(\sqrt{n})$ 次就可以了，时间复杂度是 $O(n\sqrt{n} \log n)$ 。

你说得对，但是我学过基本不等式，上面的操作都是假设块长为 $\sqrt{n}$ ，我们考虑基本不等式，设分治阈值为 $B$ ，那么第一块是 $nB$ ，第二块是 $\dfrac{n^2 \log n}{B}$ ，由基本不等式有 $B=\sqrt{n\log n}$ 时取最优时间。

代码如下：

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=1e6+15;
int n,bl,fa[MN],ans[MN],f[MN],dfn[MN],dtot;
vector<int> adj[MN];

void dfs(int u,int pre){
    fa[u]=pre;
    for(auto v:adj[u]){
        if(v==pre) continue;
        dfs(v,u);
    }
    dfn[++dtot]=u;
}

int solve(int k){
    int ret=0;
    for(int i=1;i<=n;i++) f[i]=1;
    for(int i=1;i<=n;i++){
        int u=dfn[i],pre=fa[u];
        if(pre&&f[u]!=-1&&f[pre]!=-1){
            if(f[u]+f[pre]>=k){
                ret++;
                f[pre]=-1;
            }else f[pre]=max(f[pre],f[u]+1);
        }
    }
    return ret;
}

int main(){
    cin>>n;
    bl=sqrt(n*__lg(n));
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    ans[1]=n;
    for(int i=2;i<=bl;i++){
        ans[i]=solve(i);
    }
    for(int i=bl+1;i<=n;i++){
        int tmp=solve(i);
        int l=i,r=n,cnt=i;
        while(l+1<r){
            int mid=(l+r)>>1;
            if(solve(mid)==tmp){
                cnt=max(cnt,mid);
                l=mid;
            }else r=mid;
        }
        for(;i<=cnt;i++) ans[i]=tmp;
        i--;
    }
    for(int i=1;i<=n;i++) cout<<ans[i]<<'\n';
    return 0;
}

[IOI2009] Regions

完蛋啦，又是制约关系，同时涉及两个集合的关系，并且颜色点数与总颜色数相互制约如果我们都考虑显然是不行的。根据我们前面提到的，我们考虑一下根号分治如何去做。

有两个暴力的想法：

分别枚举两个颜色中所有点，利用 DFN 判定是不是在子树内。
将一个颜色所有点加入数据结构，让后枚举另一个颜色所有点，看有多少点在当前子树。

第一个想法时间复杂度 $O(n^2)$ ，第二个空间复杂度时 $O(n^2)$ 但是时间很好。并且我们前面提到了制约关系，考虑根号分治，我们确定一个阈值 $B$ ，颜色点数 $>B$ 的我们称之为重颜色，而 $\le B$ 的我们称之为轻颜色（对应重儿子和轻儿子 www），考虑分类讨论。

重颜色作为祖先节点：考虑预处理答案，时间复杂度容易做到 $O(n\sqrt{n \log n})$ ，空间 $O(n\sqrt{n})$ 。
轻颜色作为祖先节点：枚举轻颜色所有点，考虑对于每一个颜色开 vector 按 DFN 将所有点排序，根据 DFN 顺序判断是否在子树即可，利用二分找边界即可。时间复杂度 $O(n\sqrt{n \log n})$ 。

故总时间复杂度 $O(n\sqrt{n \log n})$ ，空间复杂度 $O(n\sqrt{n})$ 。

至于为什么我用 DFN，答案是因为一开始我想的虚树，这和我说的加数据结构其实差不太多，因为虚树本身也算一种数据结构吗 www。当然每一次建虚树不如用 DFN 好写啦。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=2e5+15,ML=30,MK=2.5e4+15;
int n,r,q,ccnt[MN],fid[MN],id[MN],cf[MN],MB;
int ans[520][MK];
vector<int> adj[MN],col[MN],dcol[MN];

namespace Tree{
    int dfn[MN],siz[MN],dtot;

    void dfs(int u,int pre){
        dfn[u]=++dtot;
        siz[u]=1;
        for(auto v:adj[u]){
            if(v==pre) continue;
            dfs(v,u);
            siz[u]+=siz[v];
        }
    }

    int cmpdfn(int x,int y){
        return dfn[x]<dfn[y];
    }
}using namespace Tree;

bool cmp(int x,int y){
    return ccnt[x]>ccnt[y];
}

signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>r>>q;
    MB=sqrt(n*__lg(n)*2);
    for(int i=1;i<=n;i++){
        int fa,color;
        if(i!=1){
            cin>>fa;
            adj[fa].push_back(i);
        }
        cin>>color;
        col[color].push_back(i);
        ccnt[color]++;
    }
    for(int i=1;i<=r;i++) id[i]=i;
    sort(id+1,id+1+r,cmp);
    dfs(1,0);
    for(int i=1;i<=r;i++){
        fid[id[i]]=i;
        for(auto p:col[i]) dcol[i].push_back(dfn[p]);
        sort(dcol[i].begin(),dcol[i].end());
    }
    for(int i=1;i<=r&&ccnt[id[i]]>=MB;i++){
        for(int i=1;i<=n+1;i++) cf[i]=0;
        for(auto p:col[id[i]]){
            cf[dfn[p]]++;
            cf[dfn[p]+siz[p]]--;
        }
        for(int i=1;i<=n+1;i++){
            cf[i]+=cf[i-1];
        }
        for(int j=1;j<=r;j++){
            for(auto p:col[j]){
                ans[i][j]+=cf[dfn[p]];
            }
        }
    }
    while(q--){
        int x,y;
        cin>>x>>y;
        if(ccnt[x]<MB){
            long long ret=0;
            for(auto p:col[x]){
                ret+=upper_bound(dcol[y].begin(),dcol[y].end(),dfn[p]+siz[p]-1)-lower_bound(dcol[y].begin(),dcol[y].end(),dfn[p]);
            }
            cout<<ret<<endl;
        }else cout<<ans[fid[x]][y]<<endl;
    }
    
    return 0;
}

[JRKSJ R2] 你的名字

这种复杂的取模操作，我们一般会利用根号分治来解决这一类问题。

模数不是给定的，这种情况下很难搞，因为我们直接维护模数不固定的数据时很难搞的。

首先，静态区间询问考虑莫队，注意到给出了一个 $k>10^3$ 的包。考虑在 $k$ 很大的情况下取模所构成的循环节长度很长，并且值域只有 $10^5$ ，我们可以通过利用 bitset 来暴力跑循环节，时间复杂度为 $O(n\sqrt{m}+\dfrac{ma}{\omega}+\dfrac{ma}{k})$ ，实现用 find_first 可以偷懒循环节。

但是 $k$ 很小不能这么做，但是我们发现 $k$ 很小的时候是一个取模数列的 RMQ 啊，可以暴力预处理 $k$ 做四毛子（用传统 ST 表会炸杠）。

但是过不了，考虑若 $k$ 的询问数量很小，我们还不如和 $k\ge B$ 的询问一起处理，这样省下暴力计算的时间。我们可以通过确定一些平衡因子让其自适应数据，这样就能卡过了 www，具体如何操作可以看 meyi 的题解。

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=3e5+15,MB=1e5+15;
struct Query{
    int l,r,K,id;
};
int n,m,bl,a[MN],b[MN],ans[MN],cnt[MN];
bitset<MB> f;
vector<Query> qry[MN];

namespace ly
{
    namespace IO
    {
        #ifndef LOCAL
            constexpr auto maxn=1<<20;
            char in[maxn],out[maxn],*p1=in,*p2=in,*p3=out;
            #define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,maxn,stdin),p1==p2)?EOF:*p1++)
            #define flush() (fwrite(out,1,p3-out,stdout))
            #define putchar(x) (p3==out+maxn&&(flush(),p3=out),*p3++=(x))
            class Flush{public:~Flush(){flush();}}_;
        #endif
        namespace usr
        {
            template<typename type>
            inline type read(type &x)
            {
                x=0;bool flag(0);char ch=getchar();
                while(!isdigit(ch)) flag^=ch=='-',ch=getchar();
                while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
                return flag?x=-x:x;
            }
            template<typename type>
            inline void write(type x)
            {
                x<0?x=-x,putchar('-'):0;
                static short Stack[50],top(0);
                do Stack[++top]=x%10,x/=10;while(x);
                while(top) putchar(Stack[top--]|48);
            }
            inline char read(char &x){do x=getchar();while(isspace(x));return x;}
            inline char write(const char &x){return putchar(x);}
            inline void read(char *x){static char ch;read(ch);do *(x++)=ch;while(!isspace(ch=getchar())&&~ch);}
            template<typename type>inline void write(type *x){while(*x)putchar(*(x++));}
            inline void read(string &x){static char ch;read(ch),x.clear();do x+=ch;while(!isspace(ch=getchar())&&~ch);}
            inline void write(const string &x){for(int i=0,len=x.length();i<len;++i)putchar(x[i]);}
            template<typename type,typename...T>inline void read(type &x,T&...y){read(x),read(y...);}
            template<typename type,typename...T>
            inline void write(const type &x,const T&...y){write(x),putchar(' '),write(y...),sizeof...(y)^1?0:putchar('\n');}
            template<typename type>
            inline void put(const type &x,bool flag=1){write(x),flag?putchar('\n'):putchar(' ');}
        }
        #ifndef LOCAL
            #undef getchar
            #undef flush
            #undef putchar
        #endif
    }using namespace IO::usr;
}using namespace ly::IO::usr;

bool mdcmp(Query x,Query y){
    if(x.l/bl==y.l/bl){
        if((x.l/bl)&1) return x.r<y.r;
        return x.r>y.r;
    }
    return x.l/bl<y.l/bl;
}

signed main(){
    read(n,m);
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    for(int i=1;i<=m;i++){
        int l,r,k;
        read(l,r,k);
        qry[k].push_back({l,r,k,i});
    }
    for(int i=2;i<MN;i++){
        if(qry[i].empty()) continue;
        if(min(MB/i,MB>>6)*qry[i].size()<(n<<2)){
            qry[0].insert(qry[0].end(),qry[i].begin(),qry[i].end());
            continue;
        }
        bl=n/sqrt(qry[i].size()+1)+1;
        for(int j=1;j<=n;j++){
            b[j]=a[j]%i;
        }
        sort(qry[i].begin(),qry[i].end(),mdcmp);
        int l=1,r=0;
        for(auto p:qry[i]){
			while(l>p.l) (!cnt[b[--l]]++)&&(f[b[l]]=1);
			while(r<p.r) (!cnt[b[++r]]++)&&(f[b[r]]=1);
			while(l<p.l) (!--cnt[b[l]])&&(f[b[l]]=0),++l;
			while(r>p.r) (!--cnt[b[r]])&&(f[b[r]]=0),--r;
            for(int k=0;k<i;k++){
                if(f[k]){
                    ans[p.id]=k;
                    break;
                }
            }
        }
        f.reset();
        memset(cnt,0,sizeof(cnt));
    }
    if(!qry[0].empty()){
        bl=n/sqrt(qry[0].size()+1)+1;
        sort(qry[0].begin(),qry[0].end(),mdcmp);
        int l=1,r=0;
        for(auto p:qry[0]){
			while(l>p.l) (!cnt[a[--l]]++)&&(f[a[l]]=1);
			while(r<p.r) (!cnt[a[++r]]++)&&(f[a[r]]=1);
			while(l<p.l) (!--cnt[a[l]])&&(f[a[l]]=0),++l;
			while(r>p.r) (!--cnt[a[r]])&&(f[a[r]]=0),--r;
            ans[p.id]=1e9;
			for(int k=f._Find_first(); ans[p.id]&&k!=f.size(); k=(k/p.K+1)*p.K-1>=f.size()?f.size():f._Find_next((k/p.K+1)*p.K-1)) 
				(ans[p.id]>k%p.K)&&(ans[p.id]=k%p.K);
        }
    }
    for(int i=1;i<=m;i++) put(ans[i]);
    return 0;
}

[Ynoi2008] rplexq

我们要求的值就是 $x$ 子树内 $[l,r]$ 点个数的平法减去每个儿子子树内 $[l,r]$ 点个数的平方，让后整体除二，即子树两两配对即可。

但是暴力做是 $O(n^2)$ 的，无法接受，考虑如何优化，注意到瓶颈在枚举儿子的子树。我们从儿子下手，根号分治，对于每个节点按照儿子格式分成 $>\sqrt{n}$ 和 $\le \sqrt{n}$ 两组。

小于 $\sqrt{n}$ 的我们可以把区间拆成二维数点来动态加点进行维护，这样的点数是 $O(n)$ 个，询问时 $O(m\sqrt{n})$ ，考虑复杂度平衡，我们可以利用分块前缀和的方式进行维护，单点修改时 $O(\sqrt{n})$ ，而查询 $O(1)$ 。时间复杂度 $O((n+m)\sqrt{n})$ ，但空间是 $O(m\sqrt{n})$ 的。注意到同一个点上每个询问的询问区间相同，我们 $O(n)$ 的存下每个子树区间扫描线，扫描到一点 $x$ 在将询问进行二维数点。

而大于 $\sqrt{n}$ 这么做直接复杂度螺旋式爆炸上天，考虑涉及另一个算法，我们发现在一个区间的点可以类比于颜色，那么问题就是统计 $[l,r]$ 编号内的颜色平方和，考虑对每一个点建立离散化莫队，时间复杂度 $O(n\sqrt{m})$ ，最终时间复杂度可以平衡到 $O(n\sqrt{n}+n\sqrt{m}+q\sqrt{n})$ 。

但是可怕的是我没卡过，54 pt 代码如下：

#include<bits/stdc++.h>
#define ll long long
#define pir pair<int,int>
using namespace std;
constexpr int MN=5e5+100,MB=100,MBL=500;
struct Query{
    int l,r,id;
    ll op;
}tqry[MN];
int n,m,rt,R[MN],tmp[MN],dg[MN],pos[MN],bl;
ll ans1,ans2,ans3[MN],sum[MN],cnt[MN],ans[MN];
bool vis[MN];
vector<int> adj[MN];
vector<Query> qry[MN];

namespace Tree{
    int siz[MN],fa[MN],dfn[MN],dtot;
    pir a[MN];
    
    void dfs1(int u,int pre){
        siz[u]=1;
        fa[u]=pre;
        for(auto v:adj[u]){
            if(v==pre) continue;
            dfs1(v,u);
            siz[u]+=siz[v];
        }
    }

    void dfs2(int u,int pre){
        dfn[++dtot]=u;
        a[dtot]=pir(u,pre);
        for(auto v:adj[u]){
            if(v==pre) continue;
            dfs2(v,u);
        }
    }

}using namespace Tree;

bool cmpsiz(int x,int y){
    return siz[x]>siz[y];
}

bool cmpmd(Query x,Query y){
    if(pos[x.l]!=pos[y.l]) return pos[x.l]<pos[y.l];
    return (pos[x.l]&1)?x.r<y.r:x.r>y.r;
}

void add(int x,ll op){
    ans1+=1ll*1+cnt[x]*2*op;
    cnt[x]+=op;
    ans2+=op;
}

ll query(int x){
    return (x?(R[x]==x?sum[pos[x]]:sum[pos[x]-1]+cnt[x]):0);
}

void update(int x){
    for(int i=pos[x];i<=pos[n];i++){
        sum[i]++;
    }
    for(int i=x;i<=R[x];i++) cnt[i]++;
}

void solve1(int x){
    if(qry[x].empty()) return;
    int tmptot=0;
    for(auto v:adj[x]){
        if(v==fa[x]) continue;
        tmp[++tmptot]=v;
    }
    sort(tmp+1,tmp+1+tmptot,cmpsiz);
    dtot=0;
    for(int i=MB+1;i<=tmptot;i++){
        dfs2(tmp[i],tmp[i]);
        vis[tmp[i]]=1;
    }
    sort(a+1,a+1+dtot);
    sort(dfn+1,dfn+1+dtot);
    for(int i=0;i<qry[x].size();i++){
        int ql=lower_bound(dfn+1,dfn+1+dtot,qry[x][i].l)-dfn;
        int qr=upper_bound(dfn+1,dfn+1+dtot,qry[x][i].r)-dfn-1;
        tqry[i+1]={ql,qr,qry[x][i].id};
    }
    int l=1,r=0,bl=dtot/sqrt(qry[x].size())+1;
    for(int i=1;i<=dtot;i++){
        pos[i]=(i+bl-1)/bl;
    }
    sort(tqry+1,tqry+1+qry[x].size(),cmpmd);
    ans1=ans2=0;
    for(int i=1;i<=qry[x].size();i++){
        if(tqry[i].l>dtot||tqry[i].r<1) continue;
        while(l<tqry[i].l) add(a[l++].second,-1);
        while(l>tqry[i].l) add(a[--l].second,1);
        while(r<tqry[i].r) add(a[++r].second,1);
        while(r>tqry[i].r) add(a[r--].second,-1);
        ans[tqry[i].id]-=ans1;
        ans3[tqry[i].id]+=ans2;
    }
}

void solve2(int x){
    if(!vis[x]&&fa[x]&&!qry[fa[x]].empty()){
        for(int i=0;i<qry[fa[x]].size();i++){
            qry[fa[x]][i].op=query(qry[fa[x]][i].r)-query(qry[fa[x]][i].l-1);
        }
    }
    update(x);
    for(auto v:adj[x]){
        if(v==fa[x]) continue;
        solve2(v);
    }
    if(!vis[x]&&fa[x]&&!qry[fa[x]].empty()){
        for(int i=0;i<qry[fa[x]].size();i++){
            ll qwq=query(qry[fa[x]][i].r)-query(qry[fa[x]][i].l-1)-qry[fa[x]][i].op;
            ans[qry[fa[x]][i].id]-=qwq*qwq;
            ans3[qry[fa[x]][i].id]+=qwq;
        }
    }
    for(int i=0;i<qry[x].size();i++){
        if(qry[x][i].l<=x&&x<=qry[x][i].r){
            ans[qry[x][i].id]+=ans3[qry[x][i].id]*2;
        }
    }
}

signed main(){
    read(n,m,rt);
    for(int i=1;i<n;i++){
        int u,v;
        read(u,v);
        adj[u].push_back(v);
        adj[v].push_back(u);
        dg[u]++,dg[v]++;
    }
    for(int i=1;i<=m;i++){
        int l,r,x;
        read(l,r,x);
        qry[x].push_back({l,r,i,0});
    }
    dfs1(rt,0);
    for(int i=1;i<=n;i++){
        if(i!=rt) dg[i]--;
        if(dg[i]>MB){
            solve1(i);
        }
    }
    for(int i=1;i<=n;i++){
        pos[i]=(i+MBL-1)/MBL;
        R[i]=min(n,pos[i]*MBL);
    }
    memset(cnt,0,sizeof(cnt));
    solve2(rt);
    for(int i=1;i<=m;i++){
        put(((ans3[i]*ans3[i]+ans[i])>>1));
    }
    return 0;
}

P3591 [POI 2015] ODW

序列跳跃问题可以直接对后继的距离根号分治的。

一个显然的想法就是类似于倍增二分去模拟在树上走路（即倍增求树上 $k$ 级祖先，也可以长链剖分做），但是这在 $k$ 很大的情况下时可以的，但是 $k$ 很小的情况是做不到的。具体来说，步数接近于 $\dfrac{n}{k}$ 的范围附近。坏了又是 $\dfrac{n}{k}$ ，我们考虑根号分治，设定阈值 $B$ ， $>B$ 当然就是我们树上 $k$ 级祖先暴力跳，时间复杂度 $O(n\sqrt{n})$ 。当 $k\le B$ 的时候我们可以考虑暴力处理 $sum(i,j)$ 表示 $i$ 往上每 $j$ 级走一步的答案，查询可以树上差分即可。

时间复杂度 $O(n\sqrt{n} \log n)$ ，预处理 $O(n\sqrt{n})$ 。利用长链剖分可以做到 $O(n\log n+n\sqrt{n})$ 。

但是我写这篇文章的时候我还不会长链剖分？

#include<bits/stdc++.h>
using namespace std;
constexpr int MN=5e4+15,MB=250;
int n,a[MN],b[MN],c[MN],sum[MN],s[MB+5][MN],fa[32][MN],dep[MN];
vector<int> adj[MN];

void dfs1(int u,int pre){
    dep[u]=dep[pre]+1;
    fa[0][u]=pre;
    sum[u]=sum[pre]+a[u];
    for(int i=1;i<=30;i++){
        fa[i][u]=fa[i-1][fa[i-1][u]];
    }
    for(auto v:adj[u]){
        if(v==pre) continue;
        dfs1(v,u);
    }
}

void dfs2(int u,int pre){
    int p=pre;
    for(int i=2;i<=MB;i++){
        p=fa[0][p];
        if(p==0) break;
        s[i][u]=s[i][p]+a[u];
    }
    for(auto v:adj[u]){
        if(v==pre) continue;
        dfs2(v,u);
    }
}

int lca(int x,int y){
    if(dep[x]>dep[y]){
        swap(x,y);
    }
    for(int i=30;i>=0;i--){
        if(fa[i][y]&&dep[fa[i][y]]>=dep[x]) y=fa[i][y];
    }
    if(x==y) return x;
    for(int i=30;i>=0;i--){
        if(fa[i][x]!=fa[i][y]){
            x=fa[i][x],y=fa[i][y];
        }
    }
    return fa[0][x];
}

int getfa(int x,int k){
    for(int i=30;i>=0;i--){
        if((k>>i)&1) x=fa[i][x];
    }
    return x;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<n;i++) cin>>c[i];
    dfs1(1,0);
    dfs2(1,0);
    for(int i=1;i<n;i++){
        int u=b[i],v=b[i+1],k=c[i];
        int lcaa=lca(u,v);
        if(k==1){
            cout<<sum[u]+sum[v]-sum[lcaa]-sum[fa[0][lcaa]]<<'\n';
        }
        else if(k<=MB){
            int ans=s[k][u],dis=(dep[u]-dep[lcaa])%k;
            if(dis==0) dis=k;
            for(int i=30;i>=0;i--){
                if(fa[i][u]&&dep[fa[i][u]]-dep[lcaa]>=dis) u=fa[i][u];
            }
            ans+=a[u]-s[k][u];
            if(dep[u]+dep[v]-(dep[lcaa]<<1)>=k){
                dis=k-dep[u]+dep[lcaa];
                u=v;
                for(int i=30;i>=0;i--){
                    if(fa[i][u]&&dep[fa[i][u]]-dep[lcaa]>=dis) u=fa[i][u];
                }
                dis=(dep[v]-dep[u])%k;
                if(dis!=0) ans+=a[v];
                v=getfa(v,dis);
                ans+=s[k][v]-s[k][u]+a[u];
            }else ans+=a[v];
            cout<<ans<<'\n';
        }else{
            int ans=0;
            while(dep[u]-dep[lcaa]>k){
                ans+=a[u];
                u=getfa(u,k);
            }
            ans+=a[u];
            if(dep[u]+dep[v]-(dep[lcaa]<<1)>=k){
                int dis=k-dep[u]+dep[lcaa];
                u=v;
                for(int i=30;i>=0;i--){
                    if(fa[i][u]&&dep[fa[i][u]]-dep[lcaa]>=dis) u=fa[i][u];
                }
                dis=(dep[v]-dep[u])%k;
                if(dis!=0) ans+=a[v];
                v=getfa(v,dis);
                while(dep[v]-dep[u]>=k){
                    ans+=a[v];
                    v=getfa(v,k);
                }
                ans+=a[v];
            }else ans+=a[v];
            cout<<ans<<'\n';
        }
    }
    return 0;
}

[Ynoi2011] 初始化

如果你看了论文的话，这个就是第一题的双倍经验。

大多数的数据结构都适合连续区间的询问，但是不擅长这种间隔离散的询问，步数与项数相互制约关系，我们考虑根号分治，设定一个阈值 $B$ ，对于 $>B$ 的想法当然是暴力处理啦，但是 $\le B$ 很难受。

分析性质，我们每一次修改都是对整个序列进行修改，对于 $x,y$ 相同的修改我们可以累加贡献，但是我们查询要对所有 $x$ 的都进行一次查询，我们要做到单次 $O(1)$ 。考虑我们维护每个 $x,y$ 的前缀后缀和，我们一次询问相当于把序列按 $x$ 分块，我们借用 YLWang 的 P5309 题解的图片：

那么之间完整段会被所有含 $x$ 的操作修改，而两端会被部分修改，询问同理，我们利用前面提到的前缀后缀即可快速维护即可。

#include<bits/stdc++.h>
#define pos(x) ((x-1)/BL+1)
using namespace std;
constexpr int MN=2e5+5,MOD=1e9+7,BL=128;
int n,m,bl,a[MN],sum[MN],L[MN],R[MN],pre[BL+15][BL+15],suf[BL+15][BL+15];

inline void upd(int &x){x+=x>>31&MOD;}

void init(){
    bl=(n-1)/BL+1;
    for(int i=1;i<=bl;i++){
        L[i]=(i-1)*BL+1;
        R[i]=i*BL;
    }
    R[bl]=n;
    for(int i=1;i<=bl;i++){
        sum[i]=0;
        for(int j=L[i];j<=R[i];j++){
            sum[i]+=a[j];
            upd(sum[i]-=MOD);
        }
    }
}

int query(int l,int r){
    int ql=pos(l),qr=pos(r),ret=0;
    if(ql==qr){
        for(int i=l;i<=r;i++){ret+=a[i];upd(ret-=MOD);}
        return ret;
    }
    for(int i=l;i<=R[ql];i++){ret+=a[i];upd(ret-=MOD);}
    for(int i=ql+1;i<qr;i++){ret+=sum[i];upd(ret-=MOD);}
    for(int i=L[qr];i<=r;i++){ret+=a[i];upd(ret-=MOD);}
    return ret;
}

void add(int x,int y,int z){
    z-=MOD;upd(z);
    if(x>=BL){
        for(int i=y;i<=n;i+=x){
            a[i]+=z;upd(a[i]-=MOD);
            sum[pos(i)]+=z;upd(sum[pos(i)]-=MOD);
        }
    }else{
        for(int i=x;i>=y;i--){pre[x][i]+=z;upd(pre[x][i]-=MOD);}
        for(int i=1;i<=y;i++){suf[x][i]+=z;upd(suf[x][i]-=MOD);}
    }
}

signed main(){
    read(n);read(m);
    for(int i=1;i<=n;i++)read(a[i]);
    init();
    while(m--){
        int op,x,y,z,l,r;
        read(op);
        if(op==1){
            read(x);read(y);read(z);
            add(x,y,z);
        }else{
            read(l);read(r);
            int ret=query(l,r);
            for(int i=1;i<BL;i++){
                int blkL=(l-1)/i+1,blkR=(r-1)/i+1;
                if(blkL==blkR){
                    ret+=pre[i][(r-1)%i+1];upd(ret-=MOD);
                    ret-=pre[i][(l-1)%i];upd(ret);
                }else{
                    ret+=(blkR-blkL-1LL)*pre[i][i]%MOD;upd(ret-=MOD);
                    ret+=pre[i][(r-1)%i+1];upd(ret-=MOD);
                    ret+=suf[i][(l-1)%i+1];upd(ret-=MOD);
                }
            }
            put(ret);
        }
    }
    return 0;
}

CF1056H Detect Robots

令 $s=\sum\limits len$ 。

考虑我们答案到底是怎么算的，其实就是枚举一个串两个字符 $A\to C \to \dots \to B$ ，如果之前出现过 $A \to D \to \dots \to B$ 的路径，检查 $C$ 是否等于 $D$ 即可，若不等于输出 Human。一个显然的想法就是枚举 $A,B$ 轻松 $O(s^3)$ ，但是我们可以只需要枚举一个，比如枚举 $B$ 让后拓展即可，这样的时间复杂度 $O(s^2)$ 。如果 $s$ 过大直接就爆炸了，考虑一个关键性质：数据范围 $3 \times 10^5$ ，考虑到长为 $k$ 的路径最多有 $\dfrac{n}{k}$ 个，考虑根号分治，按串长分治。小串对小串暴力即可。

大串我们可以暴力枚举，记 $pos_{i}$ 表示 $i$ 在大串中的位置，对于其他串从后往前扫，判断当前字母的 $pos<mxpos_{i}$ 是否成立即可，时间复杂度 $O(s\sqrt{s})$ 。

#include<bits/stdc++.h>
#define pir pair<int,int>
using namespace std;
constexpr int MN=1e6+15;
int T,n,m,B,pos[MN],vis[MN];
vector<int> a[MN];
vector<pir> v[MN];

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        v[i].clear();
        vis[i]=pos[i]=0;
    }
    for(int i=1;i<=m;i++){
        a[i].clear();
        int K;
        cin>>K;
        for(int j=1;j<=K;j++){
            int x;
            cin>>x;
            a[i].push_back(x);
        }
        if(a[i].size()<=B){
            for(int j=0;j<a[i].size();j++){
                for(int k=j+1;k<a[i].size();k++){
                    v[a[i][k]].push_back(pir(a[i][j],a[i][j+1]));
                }
            }
        }
    }
    for(int i=1;i<=m;i++){
        if(a[i].size()<=B) continue;
        for(int j=1;j<=n;j++) pos[j]=-1;
        for(int j=0;j<a[i].size();j++) pos[a[i][j]]=j;
        for(int j=i+1;j<=m;j++){
            int r=-1;
            for(int k=a[j].size()-1;k>=0;k--){
                if(pos[a[j][k]]==-1) continue;
                if(pos[a[j][k]]>r){
                    r=pos[a[j][k]];
                }
                else if(a[j][k+1]!=a[i][pos[a[j][k]]+1]){
                    cout<<"Human\n";
                    return;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(auto p:v[i]){
            if(vis[p.first]&&vis[p.first]!=p.second){
                cout<<"Human\n";
                return;
            }
            vis[p.first]=p.second;
        }
        for(auto p:v[i]) vis[p.first]=0;
    }
    cout<<"Robot\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    B=sqrt(300000)/2;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

CF587F Duff is Mad

暴力的想法就是重新建 AC 自动机，不得不承认这个想法及其糟糕。

考虑直接对所有串建立 AC 自动机，那么答案就是将 $s\in [l,r]$ 上串对应 Fail 树上的权值加一后求权值和，考虑离线下来加根号分治，阈值为 $B$ ，对于 $|S_k|>B$ 的考虑将每个串询问做差，顺序扫过即可，时间复杂度 $O(n\sqrt{n})$ 。

对于 $|S_{k}| \le B$ 考虑扫描线，扫到一个串就权值加一，让后暴力查询即可，其实这两个操作都是在 DFS 序上区间加单点查，树状数组即可，时间房租啊都 $O(n \log m+QT\log m)$ 。

#include<bits/stdc++.h>
#define int long long
#define pir pair<int,int>
using namespace std;
constexpr int N=1e5+7;
int n,q,sumlen,MB,ans[N];
string s[N];
vector<int> adj[N];
vector<pir> L1[N],R1[N],L2[N],R2[N];

struct BIT{
    int t[N];

    int lowbit(int x){
        return x&-x;
    }

    void modify(int x,int k){
        while(x<N){
            t[x]+=k;
            x+=lowbit(x);
        }
    }

    int query(int x){
        int ret=0;
        while(x){
            ret+=t[x];
            x-=lowbit(x);
        }
        return ret;
    }
}bit;

namespace ACAuto{
    int trie[N][26],fail[N],fa[N],ed[N],tot=1;
    int sum[N],siz[N],dfn[N],dtot;

    void insert(string s,int id){
        int p=1;
        for(auto c:s){
            int k=c-'a';
            if(!trie[p][k]) trie[p][k]=++tot,fa[tot]=p;
            p=trie[p][k];
        }
        ed[id]=p;
    }

    void build(){
        queue<int> q;
        for(int i=0;i<26;i++){
            if(trie[1][i]) fail[trie[1][i]]=1,q.push(trie[1][i]);
            else trie[1][i]=1;
        }
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=0;i<26;i++){
                if(trie[x][i])
                    fail[trie[x][i]]=trie[fail[x]][i],q.push(trie[x][i]);
                else trie[x][i]=trie[fail[x]][i];
            }
        }
        for(int i=2;i<=tot;i++) adj[fail[i]].push_back(i);
    }

    void dfs1(int u){
        for(auto v:adj[u]){
            dfs1(v);
            sum[u]+=sum[v];
        }
    }

    void dfs2(int u){
        siz[u]=1;
        dfn[u]=++dtot;
        for(auto v:adj[u]){
            dfs2(v);
            siz[u]+=siz[v];
        }
    }
}using namespace ACAuto;

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        sumlen+=s[i].length();
        insert(s[i],i);
    }
    build();
    MB=sumlen/sqrt(q*log2(sumlen));
    
    for(int i=1;i<=q;i++){
        int l,r,k;
        cin>>l>>r>>k;
        if(s[k].length()>MB){
            L1[k].emplace_back(l,i);
            R1[k].emplace_back(r,i);
        }else{
            L2[l].emplace_back(k,i);
            R2[r].emplace_back(k,i);
        }
    }

    for(int i=1;i<=n;i++){
        if(s[i].length()>MB){
            int p=ed[i];
            while(p!=1) sum[p]=1,p=fa[p];
            dfs1(1);
            sort(L1[i].begin(),L1[i].end());
            sort(R1[i].begin(),R1[i].end());
            reverse(L1[i].begin(),L1[i].end());
            reverse(R1[i].begin(),R1[i].end());
            int tmp=0;
            for(int j=1;j<=n;j++){
                while(L1[i].size()&&L1[i].back().first==j){
                    ans[L1[i].back().second]-=tmp;
                    L1[i].pop_back();
                }
                tmp+=sum[ed[j]];
                while(R1[i].size()&&R1[i].back().first==j){
                    ans[R1[i].back().second]+=tmp;
                    R1[i].pop_back();
                }
            }
            for(int i=2;i<=tot;i++) sum[i]=0;
        }
    }

    dfs2(1);
    for(int i=1;i<=n;i++){
        for(auto [k,id]:L2[i]){
            int p=ed[k];
            while(p!=1) ans[id]-=bit.query(dfn[p]),p=fa[p];
        }
        bit.modify(dfn[ed[i]],1);
        bit.modify(dfn[ed[i]]+siz[ed[i]],-1);
        for(auto [k,id]:R2[i]){
            int p=ed[k];
            while(p!=1) ans[id]+=bit.query(dfn[p]),p=fa[p];
        }
    }

    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
    return 0;
}

3. 后言

根号分治，做那么多题其实就是根号平衡时空复杂度。注意分治后的情况下具有的性质，同时对次数分类讨论就可以了。

1. 介绍与引入

2. 例题

3. 后言

4. 参考