平衡规划

平衡规划小记。

0.前言

平衡规划其实也可以算是一种思想，他其实是不同算法的综合， 出题人为了增加你的码量和思维难度而产生的新的做法，但一般 良心点的出题人对于想到一个都还是会给较多的分数的。

——mydcwfy

平衡规划大致分为以下四种：

​ 1.隐含的和相同，然后可以根号或者是其他之类的分治。一般有序列出现次数和为 $\mathcal O(n)$ 和图的度数和为 $\mathcal O(m)$ 两种。

​ 2.题面给定 $n + m$ 或 $n\times m$，然后按照 $n,m ≤ \sqrt{n\times m}$ 或 $n, m ≤ \frac{n + m}{ 2}$ 分治。

​ 3.题目给定 $n$，容易计算 $\sqrt n$ 以内的答案且有规律性，用 $\sqrt n$ 个答案来合并出总答案。也有可能是利用 $\frac{n}{2}$ 合并两端。

​ 4.不同算法因为切入点不同，得到的时间复杂度不同，比如 $O(nB)$ 和 $O(\frac{n^2}{B} )$，合适的平衡他们，让最劣复杂度最优。

接下来以例题为主介绍平衡规划的思想。

1.出现次数和一定

经典，很多时候看到与出现次数相关就可以考虑平衡规划。

1.1 P8349 [SDOI/SXOI2022] 整数序列

我们分为几种情况来考虑，设阈值 $B$，出现次数为 $cnt_x$ 表示 $x$ 的出现次数。当 $cnt_x\le B$ 我们称之为“小“，否则称为”大“。我们容易想到把每个数的位置拿出来做是相对容易的。

1.小对小

我们直接暴力做，把 $x,y$ 出现的位置单独拉出来，前缀 min 统计一下即可。时间复杂度 $\mathcal O(q(cnt_x+cnt_y))=\mathcal O(qB)$。

2.大对大

我们发现大对大的情况其实很少，种类不超过 $\frac{n}{B}$ 个。所以我们还是暴力做，用 map 记忆化一下即可。时间复杂度 $\displaystyle \mathcal O(\frac{n^2}{B})$。

3.小对大

我们发现还是有很多位置是

2.度数和一定

有些图论题目比较感觉复杂度假的但是又严重跑不满，和度数相关的，可以考虑用度数平衡规划。

2.1 Dinic 求解二分图最大匹配复杂度证明

众所周知，用 Dinic 求解二分图最大匹配复杂度是 $\mathcal O(m\sqrt n)$，这是如何证明的呢？

先考虑一个结论，当我们使用 Dinic 进行增广时，每个当前增广路的长度一定比上一次更长。因为 Dinic 是多路增广，长度相同或者更短的增广路会在前面更新。

单次增广的时间复杂度是 $\mathcal O(m)$ 的。我们不妨设当前已经进行了 $B$ 轮，之后新一轮增广的增广路长度必然大于 $B$，这样不交的路径一定只有不超过 $\displaystyle \frac{n}{B}$ 条。而每条边最多进行一次增广，那么后半部分的时间复杂度为 $\displaystyle \mathcal O(\frac{nm}{B})$。

于是我们得到两部分的时间复杂度分别为为 $\displaystyle \mathcal O(mB),\mathcal O(\frac{nm}{B})$。平衡规划一下， $\displaystyle \mathcal O(mB)=\mathcal O(\frac{nm}{B})$，取 $B=\sqrt n$ 得到其时间复杂度为 $\mathcal O(m\sqrt n)$。

2.2 P1989 无向图三元环计数

经典题，我们暴力做有几种。枚举两条边是 $\mathcal O(m^2)$ 的；枚举一个点及其对边是 $\mathcal O(nm)$ 的；枚举 $u$ 及其可达点 $v$，与 $v$ 可达点 $w$ 是 $\mathcal O(\sum_i \deg_i^2)$ 的。

考虑优化第三个算法，先统计每个点的度数，我们只保留度数小的点连向度数大的点的边，然后直接使用第三个算法。我们接下来说明这样复杂度 $\mathcal O(m\sqrt m)$。

首先我们这样建出来的是一个 DAG。考虑每条边 $(u,v)$ 的贡献就是 $\text{out}_v$。显然复杂度是 $\sum_{i=1}^m out_{v_i}$，而对于 $\deg_v=i$，$\text{out}_v$ 显然有两个上界 $i,\frac{m}{i}$，而对 $\min(i,\frac{m}{i})$ 平衡规划，那么上界就是 $\sqrt m$。所以时间复杂度为 $\mathcal O(m\sqrt m)$。

Code

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=1e5+10,M=2e5+10;
template<class T>
inline void read(T &x)
{
    x=0;int f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m;
int u[M],v[M];
int deg[N];
vector<int>e[N];
bool vis[N];
int main()
{
    read(n,m);
    for(int i=1;i<=m;i++)read(u[i],v[i]),deg[u[i]]++,deg[v[i]]++;
    for(int i=1;i<=m;i++)
    {
        if(u[i]>v[i])swap(u[i],v[i]);
        if(deg[u[i]]>deg[v[i]])swap(u[i],v[i]);
        e[u[i]].push_back(v[i]);
    }
    int ans=0;
    for(int u=1;u<=n;u++)
    {
        for(auto v:e[u])vis[v]=1;
        for(auto v:e[u])
            for(auto w:e[v])
                ans+=vis[w];
        for(auto v:e[u])vis[v]=0;
    }
    printf("%d\n",ans);
    return 0;
}

3.不同算法的平衡规划

3.1 CF1207E Remainder Problem

经典例题。我们注意到“取模”这个很好的条件。设阈值为 $B$，容易设计以下连个暴力：

​ 1.修改：直接对 $a[x]$ 修改，$\displaystyle \mathcal O(1)$；查询：枚举 $k$，直接查询 $a[kx+y]$ 的和，$\displaystyle \mathcal O(\frac{n}{B})$。

​ 2.设数组 $cnt[i][j]$ 表示 $x\equiv j\pmod i$ 位置上 $a[x]$ 之和。修改：枚举 $i$，对 $cnt[i][x\pmod i]$ 进行修改，$\displaystyle \mathcal O(B)$；查询：答案为 $cnt[x][y]$，时间复杂度 $\mathcal O(1)$。

那么我们直接对两个算法进行平衡规划。$\displaystyle \mathcal O(\frac{n}{B})=\mathcal O(B)$，取 $B=\sqrt n$。得到时间复杂度为 $\displaystyle \mathcal O(n\sqrt m)$。

Code

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
using ll = long long;
const int N=5e5+10,M=750+5;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,q,B;
int a[N];
ll cnt[M][M];
int main()
{
    n=5e5,B=sqrt(n)+1;
    read(q);
    while(q--)
    {
        int op,x,y;
        read(op,x,y);
        if(op==1)
        {
            a[x]+=y;
            for(int i=1;i<=B;i++)cnt[i][x%i]+=y;
        }
        else
        {
            if(x<=B)printf("%lld\n",cnt[x][y]);
            else
            {
                ll ans=0;
                for(int i=y;i<=n;i+=x)ans+=a[i];
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}