根号分治简介

· · 个人记录

根号分治，顾名思义，就是将数据范围[1 \dots n]从 \sqrt{n}处分开，前[1 \dots \sqrt{n}]个按照第种方式处理，后面的按照另一种方式处理。

还是先给大家一个简单例题引入一下吧:

CF 1207F. Remainder Problem

(没错就是这场EducationalRound 我只做了ACEF...)

题目大意：

初始有一个序列，长度为n，全部为0。下标从1开始。

然后有k次询问或操作。

第一种操作是将a_x加上y

第二种操作就是求出\sum_{i∈ \operatorname{R(x,y)} }a_i

$1 \le n,k \le 5 \times 10^5

如果你在3s内就看出这题的做法，那么您就可以不用看这篇日报了。。。

如果暴力的话，那么我们可以发现，复杂度是O(n \times k)的，明显是过不去的。

所以我们可以将求和操作拆成两部分：

如果x \le \sqrt{n}，那么循环累加的次数是一定大于等于\frac{n}{\sqrt{n}}=\sqrt{n}的。幸运的是，这一类数的数量不会超过\sqrt{n}，所以我们可以单独的把它们处理起来。

反之，那么循环累加的次数一定是小于等于\frac{n}{\sqrt{n}}=\sqrt{n}的。所以这一类数可以直接暴力。

总复杂度O(k \times \sqrt{n})完美结束。撒花

Code:

//这个751只是随便找了一个与sqrt(n)接近的数。这种数都是玄学。
#include<bits/stdc++.h>
#define ll long long
#define mp make_pair
using namespace std;
ll sum[755][755],a[500005];
int main(){
    ios_base::sync_with_stdio(false);cin.tie(0),cout.tie(0);
    int q;cin>>q;
    for(;q--;){
        int tp,x,y;cin>>tp>>x>>y;
        if(tp==1){
            for(int i=1;i<751;++i)sum[i][x%i]+=y;
            a[x]+=y;
        }else{
            if(x<751){
                cout<<sum[x][y]<<endl;
            }else{
                ll rt=0;
                for(int i=y;i<=500000;i+=x)rt+=a[i];
                cout<<rt<<endl;
            }
        }
    }
}

好了，到了这里，大家应该明白根号分治的基础思路了吧。就是利用复杂度接近反比例函数的性质，将前面的\sqrt{n}个数分成一组单独处理，后n-\sqrt{n}个数直接类似于暴力的处理。

再给大家介绍一道例题吧

[APIO2015]雅加达的摩天楼

题意十分明了。

如果你搜索过了那么还是想想正解吧

题解:借用了@GoldenPotato137 大佬的题解Orz （写不过TA）

有一个一眼贪心想法：对于每只doge，我们都暴力地去建它连向它能跳到的点的边，边权为跳的次数。然后直接求一遍单元最短路即可。

很显然，这玩意的边的数量是O(n^2)的，求一遍最短路的复杂度达到了惊人

这显然是要T飞的，但是我们会从中发现一个问题：既然一个doge的跳跃是多步的，那我们能否直接把几步拆开来，然后省略重复的边？ 例如：

优化为： 这样做看起来很星，很不幸的是，这样是不行的。因为我们在计算最短路的时候，我们有可能直接从中间某个点出发，但是很不幸的是，这样是不可行的。

怎么办呢？这时我们可以考虑把网络流的分层图那一套搬出来。 我们可以考虑使用“拆点”的做法来限制从某个点出发去更新别的点的最短路。 考虑把一个点拆分为size个点，每个拆分点的含义为所有一次跳x步的都从它出发，并到达它那里。

从每个点的拆分点出发，向它的原点连一条边权为0的有向边

如果能从某个点出发，则对应的从原点连向那个跳x格远的分点连一条边权为0的边

接下来我们从每个点的对应的跳x格远的的点连向其他的点的跳x格的点，边权为1

一图胜千言： 变为 最后一行的所有点即为原来的点 从下往上第x行的点即为某个原点的第x个分点

通过这样一轮拆分，我们就已经可以解决问题啦。

啥？你说这样会有n^2个点？这是就得用到根号分治思想啦。你想，如果一个doge一次能跳的距离超过\sqrt{n}格远，那总共连出来的边不会超过\sqrt{n}条，我们直接在原点连就好啦qwq。

同样，这个分界点的取值还是一个玄学的数。

敲黑板 这里是重点！

Code:

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=30000+100;
const int M=100+20;
struct edge
{
    int to,w;
    edge (int x,int y)
    {
        to=x,w=y;
    }
};
vector <edge> e[N*M];
int n,m,size,dis[N*M],S,T;
void spfa()
{
    static int InQueue[N*M],mqueue[N*M*10],front,tail;
    memset(dis,0x3f,sizeof dis);
    front=tail=0;
    mqueue[tail++]=S*size,dis[S*size]=0;
    while(tail>front)
    {
        int now=mqueue[front++];
        InQueue[now]=false;
        for(int i=0;i<int(e[now].size());i++)
            if(dis[e[now][i].to]>dis[now]+e[now][i].w)
            {
                dis[e[now][i].to]=dis[now]+e[now][i].w;
                if(InQueue[e[now][i].to]==false)
                {
                    InQueue[e[now][i].to]=true;
                    mqueue[tail++]=e[now][i].to;
                }
            }
    }
}
int main()
{
    //freopen("3645.in","r",stdin);
    //freopen("3645.out","w",stdout);

    int t=clock();
    n=read(),m=read();
    size=min(int(sqrt(n)),50);
    int to=n*size;
    for(int i=1;i<=to;i++)
        e[i].reserve(4);
    for(int i=0;i<n;i++)
        for(int j=1;j<size;j++)
            e[i*size+j].push_back(edge(i*size,0));
    for(int i=1;i<=m;i++)
    {
        int b=read(),p=read();
        if(i==1) S=b;
        if(i==2) T=b;
        if(p>=size)
        {
            for(int j=b+p,k=1;j<n;j+=p,k++)
                e[b*size].push_back(edge(j*size,k));
            for(int j=b-p,k=1;j>=0;j-=p,k++)
                e[b*size].push_back(edge(j*size,k));
        }
        else
        {
            e[b*size].push_back(edge(b*size+p,0));
            for(int j=b;j<n-p;j+=p)
            {
                bool OK=false;
                for(int k=0;k<int(e[j*size+p].size());k++)
                    if(e[j*size+p][k].to==(j+p)*size+p)
                    {
                        OK=true;
                        break;
                    }
                if(OK==true) break;
                e[j*size+p].push_back(edge((j+p)*size+p,1));
            }
            for(int j=b;j>=p;j-=p)
            {
                bool OK=false;
                for(int k=0;k<int(e[j*size+p].size());k++)
                    if(e[j*size+p][k].to==(j-p)*size+p)
                    {
                        OK=true;
                        break;
                    }
                if(OK==true) break;
                e[j*size+p].push_back(edge((j-p)*size+p,1));
            }
        }
    }

    spfa();  //求最短路

    if(dis[T*size]<0x3f3f3f3f)
        printf("%d",dis[T*size]);
    else
        printf("-1");
    cerr<<clock()-t;
    return 0;
}

其实这一类的题目数量并不多，但是遇上了估计也只用这样做才可以了。

还是找到了一道例题:CF1039D You Are Given a Tree

放在结尾的BB:

俗话所得好，“调参要从娃娃抓起”

这个临界值就是一个标准的调参。

理论上来说是设置在\sqrt{n}，但是，由于种种玄学的原因和不确定因素，所以，这个参数往往需要自己经过无数次的尝试(TLE)后才能得到。

作者时比较喜欢用n^{0.618}做为临界值的。这里仅供参考。

int size=pow(n,0.618);

完结撒花