update:2025/11/26 17:43 修订了复杂度错误。

分析

首先注意到向下移动的操作并不重要，可以转化为求经过一次右移最后每一列有多少方块。

据此，有个很好想的

n^2

做法，我们对于所有方块求出最后它移动到那一列，但是

n\le 5\times10^5

的数据范围显然不可通过。考虑优化。

注意到每行某个位置是否有方块的信息只有

\mathcal{O}(n)

次改变，而每行某个位置是否有隔板的信息也只有

\mathcal{O}(n)

次改变。那么如果某些列多次改变后不受影响，那么它们对于答案的贡献就是相同的，那么对于这些位置的方块多次统计贡献就劣了。

考虑优化计入贡献的过程，既然改变只有

\mathcal{O}(n)

次，那么只要能够做到在贡献改变之前计入就能够优化计入次数。

具体地，对于邻近的两块隔板间的部分称作一个联通块，那么当联通块内部方块数量改变时，我们通过上次计入贡献行数与当前行数做差求得有多少行贡献相同，然后通过联通块内方块数求得应该得到贡献的区间。

如下图所示：

我们从下往上截取了样例的每一行。

第一行有 $4$ 个联通块。
第二行第三个存在的隔板消失，于是联通块 $3$ 和联通块 $4$ 合并为一个联通块，计入合并的两个联通块之前的贡献，也就是区间 $[4,4]$ 加 $1$ 。
第三行第三个方块消失了，联通块 $2$ 的贡献将改变，于是计入其之前的贡献即区间 $[2,3]$ 加 $2$ 。
第四行第三个方块消失了，计入贡献即区间 $[5,5]$ 加 $2$ 。同时，存在的第一个隔板消失，联通块 $1,2$ 合并，计入两者之前贡献即区间 $[1,1]$ 加 $3$ ，区间 $[3,3]$ 加 $1$ 。
第五行最后一个隔板消失，同上述策略计入贡献即区间 $[3,4]$ 加 $1$ 。
第六行所有方块消失，按上述方法统计贡献即可。

合并联通块的操作总次数是

\mathcal{O}(n)

，方块消失总次数是

\mathcal{O}(n)

的，单次计入答案使用差分复杂度

\mathcal{O}(1)

，但是合并操作使用到并查集总复杂度是

\mathcal{O}(n\alpha(n))

。

code

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int read(){
	int x=0,f=1;char ch=getchar();
	while('0'>ch||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,a[N],h[N],fa[N],sum[N],ans[N],ti[N],l[N],r[N]; 
vector<int>dela[N],delh[N];
int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}
int main(){
	n=read();
	for(int i=1;i<=n;i++){
		fa[i]=l[i]=r[i]=i;
		sum[i]=1;a[i]=read();
		dela[a[i]].emplace_back(i);
	}
	for(int i=1;i<n;i++)
		delh[h[i]=read()].emplace_back(i);
	for(int t=0;t<=n;t++){
		for(int i:dela[t]){
			int f=findfa(i);
			ans[r[f]-sum[f]+1]+=t-ti[f];
			ans[r[f]+1]-=t-ti[f];
			sum[f]--;
			ti[f]=t;
		}
		for(int i:delh[t]){
			int x=findfa(i),y=findfa(i+1);
			if(ti[x]<t){
				ans[r[x]-sum[x]+1]+=t-ti[x];
				ans[r[x]+1]-=t-ti[x];
			}
			if(ti[y]<t){
				ans[r[y]-sum[y]+1]+=t-ti[y];
				ans[r[y]+1]-=t-ti[y];
			}
			sum[x]+=sum[y];
			r[x]=r[y];
			fa[y]=x;
			ti[x]=t;
		}
	}
	for(int i=1;i<=n;i++)printf("%d ",ans[i]+=ans[i-1]);
	return 0;
}

题解：CF2172J Sliding Tiles

文章操作

分析

code

相关推荐

评论

题解：CF2172J Sliding Tiles