AT_abc390_f [ABC390F] Double Sum 3 点边容斥做法 题解

Zi_Gao · 2025-01-26 15:45:50 · 题解

首先我们了解一下点边容斥，目标是数一个树上的联通块个数，我们知道一棵树有 n 个点，那么就有 n-1 条边，所以只需要数所有的点个数减去所有的边个数就行。

那么这道题实际上是一条链数联通块，那么同样这样数就行，从左到右扫描线，记录每个点 a_i 上一次出现的位置 p_{a_i}，那么固定 R 到 i，对于所有的 L，会贡献 i-p_{a_i} 个点。

现在来看边，会影响的只有两条边，到 a_i-1 和 a_i+1，分析一下到 a_i-1，那么需要算出 L\in(p_{a_i},i] 贡献多少条边，那么就是 \max(p_{a_{i}-1}-p_{a_i},0)，到 a_i+1 同理。

代码很简洁，轻松最优解：

#include<bits/stdc++.h>

int pre[300010];

int main(){
    int i,j,a,n;
    long long res=0,cnt=0;
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d",&a),res+=(cnt+=i-pre[a]-std::max(pre[a-1]-pre[a],0)-std::max(pre[a+1]-pre[a],0)),pre[a]=i;

    printf("%lld",res);

    return 0;
}