题解：CF2172J Sliding Tiles

_qhbd_ · 2025-11-26 12:09:06 · 题解

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

#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;
}