题解：AT_abc420_f [ABC420F] kirinuki

先预处理出每个位置可以向上延长几个，记作

a_{i,j}

。

注意到

\lfloor\dfrac{k}{i}\rfloor

一共只有

\sqrt k

种，于是考虑按照

a

从大往小加入，然后你就知道连着的横的最多有

\lfloor\dfrac{k}{a_{i,j}}\rfloor

个，然后每次这个值变化的时候重构每种长度连续段的贡献，每次加入的时候维护连续段的长度和每种长度的出现次数即可。

时间复杂度

O(nm+m\sqrt k)

，你会发现其实就是

O(nm+\min\{n,m\}\sqrt{k})=O(nm)

。

code

CPP

#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3fLL
#define double long double 
#define eps 1e-8
#define endl '\n'
using namespace std;
const int N=5e5+5;
int n,m,k,ans,res,f[N],cnt[N];
vector<int> a[N],l[N],r[N];
vector<char> c[N];
vector<bool> b[N];
vector<pair<int,int> > v[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	if(n>m){
		for(int i=1;i<=n;++i) a[i].resize(m+1),b[i].resize(m+1),c[i].resize(m+1),l[i].resize(m+1),r[i].resize(m+1);
		for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>c[i][j];
	} else{
		for(int i=1;i<=m;++i) a[i].resize(n+1),b[i].resize(n+1),c[i].resize(n+1),l[i].resize(n+1),r[i].resize(n+1);
		for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>c[j][i];
		swap(n,m);
	}
	for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){
		if(c[i][j]=='#') a[i][j]=0;
		else{
			a[i][j]=1;
			if(i>1) a[i][j]+=a[i-1][j];
		}
		v[a[i][j]].emplace_back(make_pair(i,j));
	}
	for(int i=n;i;--i){
		if(i==n||k/i!=k/(i+1)){
			for(int j=1;j<=m;++j)
				if(j<=k/i) f[j]=j*(j+1)/2;
				else f[j]=j*(k/i)-(k/i)*(k/i+1)/2+(k/i);
			res=0;
			for(int j=1;j<=m;++j) res+=cnt[j]*f[j];
		}
		for(auto p:v[i]){
			int x=p.first,y=p.second;
			if((y>1&&b[x][y-1])&&(y<m&&b[x][y+1])){
				res-=f[(y-1)-l[x][y-1]+1]+f[r[x][y+1]-(y+1)+1],--cnt[(y-1)-l[x][y-1]+1],--cnt[r[x][y+1]-(y+1)+1];
				r[x][l[x][y-1]]=r[x][y+1],l[x][r[x][y+1]]=l[x][y-1];
				res+=f[r[x][y+1]-l[x][y-1]+1],++cnt[r[x][y+1]-l[x][y-1]+1];
			} else if(y>1&&b[x][y-1]){
				res-=f[(y-1)-l[x][y-1]+1],--cnt[(y-1)-l[x][y-1]+1];
				r[x][l[x][y-1]]=y,l[x][y]=l[x][y-1];
				res+=f[y-l[x][y-1]+1],++cnt[y-l[x][y-1]+1];
			} else if(y<m&&b[x][y+1]){
				res-=f[r[x][y+1]-(y+1)+1],--cnt[r[x][y+1]-(y+1)+1];
				l[x][r[x][y+1]]=y,r[x][y]=r[x][y+1];
				res+=f[r[x][y+1]-y+1],++cnt[r[x][y+1]-y+1];
			} else{
				res+=f[1],++cnt[1];
				l[x][y]=r[x][y]=y;
			}
			b[x][y]=1;
		}
		ans+=res;
	}
	cout<<ans<<endl;
	return 0;
}

题解：AT_abc420_f [ABC420F] kirinuki

文章操作

相关推荐

评论

题解：AT_abc420_f [ABC420F] kirinuki