[算法日常] 根号分治

根号分治

总结：玄学。

难度：玄学。

方法：砍时间复杂度。

根号分治是一种在对数据规模分类讨论的基础上利用不同算法平衡复杂度的思想。

具体看样例题目。

题目

洛谷 P8572 [JRKSJ R6] Eltaw。

读完题，不难想出前缀和的思想，用 $a_{i,j}$ 表示第 $i$ 个序列的第 $j$ 位前的数字和，俗称前缀和。

分析一下时间复杂度。

如果暴力：

#include<bits/stdc++.h>
using namespace std;
#define ljl long long
const ljl N=5e5+5;
ljl n,k,q,c[750][750];
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>k>>q;
	ljl a[k+1][n+1];memset(a,0,sizeof(a));
	for(ljl i=1;i<=k;++i)
	{
		for(ljl j=1;j<=n;++j)
		{
			ljl t;
			cin>>t;a[i][j]=a[i][j-1]+t;
		}
	}
		
			
//	if(n<=700)
//	{
//		for(ljl t=1;t<=k;++t)
//			for(ljl i=1;i<=n;++i)
//				for(ljl j=1;j<=n;++j)
//					c[i][j]=max(c[i][j],a[t][j]-a[t][i-1]);
//		while(q--)
//		{
//			ljl l,r;
//			cin>>l>>r;
//			cout<<c[l][r]<<'\n';
//		}
//		return 0;
//	}
	while(q--)
	{
		ljl l,r,maxn=0;
		cin>>l>>r;
		for(ljl i=1;i<=k;++i)
			maxn=(ljl)max(maxn,a[i][r]-a[i][l-1]);
		cout<<maxn<<'\n';
	}
	return 0;
}

别看注释，那是正解

这样的时间复杂度是 $O(qk)$ 的，显然会 T 飞。

另一种暴力：

#include<bits/stdc++.h>
using namespace std;
#define ljl long long
const ljl N=5e5+5;
ljl n,k,q,c[750][750];
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>k>>q;
	ljl a[k+1][n+1];memset(a,0,sizeof(a));
	for(ljl i=1;i<=k;++i)
	{
		for(ljl j=1;j<=n;++j)
		{
			ljl t;
			cin>>t;a[i][j]=a[i][j-1]+t;
		}
	}
		
			
//	if(n<=700)
//	{
		for(ljl t=1;t<=k;++t)
			for(ljl i=1;i<=n;++i)
				for(ljl j=1;j<=n;++j)
					c[i][j]=max(c[i][j],a[t][j]-a[t][i-1]);
		while(q--)
		{
			ljl l,r;
			cin>>l>>r;
			cout<<c[l][r]<<'\n';
		}
		return 0;
//	}
	//return 0;
}

这样子的时间复杂度即为 $O(k{n}^2)$，等于 $O(5\cdot 10^{5}n)$，也会炸飞。

这时候，注意到 $nk\le 5\times 10^5$。

那么我们设 $s=nk$。

当 $n>\sqrt{s}$ 时，$k$ 会比 $n$​ 小，则第一种暴力更优。

时间复杂度进化为 $O(q\sqrt{nk})$，用计算器 算了算，也就大概 $3\times 10^8$ 左右，开个 O2，能过。

当 $k>\sqrt{s}$ 时，$n$ 更小，显然第二种暴力更优。

时间复杂度进化为 $O(sn)$，由于 $n$ 比较小，所以也不会炸。

那么就特判一下吧，$\sqrt{5\times 10^5}$ 大概是 700 多，不妨就以 700 为分界点。

AC CODE：

#include<bits/stdc++.h>
using namespace std;
#define ljl long long
const ljl N=5e5+5;
ljl n,k,q,c[750][750];
int main(){
	ios::sync_with_stdio(0);
	cin>>n>>k>>q;
	ljl a[k+1][n+1];memset(a,0,sizeof(a));
	for(ljl i=1;i<=k;++i)
	{
		for(ljl j=1;j<=n;++j)
		{
			ljl t;
			cin>>t;a[i][j]=a[i][j-1]+t;
		}
	}
		
			
	if(n<=700)
	{
		for(ljl t=1;t<=k;++t)
			for(ljl i=1;i<=n;++i)
				for(ljl j=1;j<=n;++j)
					c[i][j]=max(c[i][j],a[t][j]-a[t][i-1]);
		while(q--)
		{
			ljl l,r;
			cin>>l>>r;
			cout<<c[l][r]<<'\n';
		}
		return 0;
	}
	while(q--)
	{
		ljl l,r,maxn=0;
		cin>>l>>r;
		for(ljl i=1;i<=k;++i)
			maxn=(ljl)max(maxn,a[i][r]-a[i][l-1]);
		cout<<maxn<<'\n';
	}
	return 0;
}