根号分治

· · 个人记录

根号分治

将一组询问按照某个值域来划分（通常取根号）不超过 x 时一种做法，超过 x 另一种做法

例题1（P3396 哈希冲突）

for(int i=y;i<=n;i+=x)

这是暴力算法的单次操作，不难看出当 x 足够大时暴力并不慢，当 x>=sqrt(n) 时，时间复杂度为 O(sqrt(n)) ,当 x<=sqrt 时，我们可以 O(n * sqrt(n)) 预处理 O(1) 回答,修改单个 x<=sqrt(n) 的值只需要 O(sqrt(n)) ,总时间复杂度为 O(m * sqrt(n)) 级别

正解：

#include<bits/stdc++.h>
using namespace std;
int a[150005];
int n,m,x,y;
long long dp[400][400];
char C;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){//输入
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)//预处理x<=sqrt(n)的答案
        for(int j=1;j<=sqrt(n);j++)
            dp[j][i%j]+=a[i]; 
    while(m--){
        cin>>C;
        cin>>x>>y;      
        if(C!='A'){
            for(int i=1;i<=sqrt(n);i++)//修改单个值把每一次旧的计数换成新的
                dp[i][x%i]+=y-a[x]; 
            a[x]=y;
        }
        else{
            if(x<=sqrt(n)) cout<<dp[x][y]<<endl; 
            else{
                long long ans=0;
                for(int i=y;i<=n;i+=x) ans+=a[i];//x>sqrt(n)
                cout<<ans<<endl;
            }
        } 

    } 
    return 0;
}

例题2（CF103D Time to Raid Cowavans）

1.将公差k按根号分治，暴力枚举，单次时间复杂度 O(sqrt(n))

2.设 dp[i][j] 表示首项为 i ，公差为 j 的区间和

3.离线数据，将公差排序，公差相同的一起计算

正解： ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int t,k; int m,n; int a[310000]; int dp[310000]; int rec[310000]; struct que{ int id; int t; int k; }q[310000]; bool cmp(que a,que b){ return a.k<b.k; } void help(int kk){ for(int i=0;i<=309999;i++) dp[i]=0; for(int i=n;i>=1;i--){ dp[i]=dp[i+kk]+a[i]; } } signed main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; } cin>>m; for(int i=1;i<=m;i++){ cin>>t>>k; q[i].t=t; q[i].k=k; q[i].id=i; } sort(q+1,q+1+m,cmp); for(int i=1;i<=m;i++){ if(q[i].k!=q[i-1].k && q[i].k<=500){ help(q[i].k); } if(q[i].k<=500 && q[i].t<=n){ rec[q[i].id]=dp[q[i].t]; } else{ for(int j=q[i].t;j<=n;j+=q[i].k){ rec[q[i].id]+=a[j]; } } } for(int i=1;i<=m;i++){ cout<<rec[i]<<endl; } return 0; } ``` ### 例题3（[CF1580C Train Maintenance](https://www.luogu.com.cn/problem/CF1580C)) 1.一辆车就是一个周期 $x[i]+y[i]

2.以 sqrt(m) 为界，当周期超过段数时，则段数 不超过 sqrt(m) ，暴力枚举，区间修改（差分，线段树，分块）

3.若周期不超过 sqrt(m) ，则周期的种类也不超过 sqrt(m) , dp[i][j] 表示周期为 i 的列车在模 i 余数为 j 天的维修的车数 对于第 k 种车，周期 i=x[k]+y[k] ，将其贡献添加到 dp[i][j] 中去

#include<bits/stdc++.h>
using namespace std;
int x[200005],y[200005];
int tim[200005],cnt[3005][3005];
int n,m,c[200005];
void add(int x,int s){
    if(x>m)return;
    c[x]+=s;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    //lkhjlkhl
    int S=min(m+0.0,sqrt(m+0.5)),lst=0;
    for(int l=1;l<=m;l++){
        int op,k;
        cin>>op>>k;
        //dsgsdfhsdrysdh
        int aa=3-2*op;
        if(op==1)tim[k]=l;
        if(x[k]+y[k]>S){
            for(int i=tim[k]+x[k];i<=m;i+=x[k]+y[k])
                add(max(i,l),aa),add(max(l,i+y[k]),-aa);
        }
        else{
            for(int i=tim[k]+x[k];i<tim[k]+x[k]+y[k];i++)
                cnt[x[k]+y[k]][i%(x[k]+y[k])]+=aa;
        }
        //hjfnhbfvbn
        int ans=lst+c[l];
        lst=ans;
        for(int i=1;i<=S;i++)ans+=cnt[i][l%i];
        printf("%d\n",ans);
    }
    //pouiudjh
    return 0;
}