「Codeforces 1151E」Number of Components

题目链接:Codeforces 1151E

Kremland 的王国是有 $n$ 个节点的树,第 $i$ 个节点有权值 $a_i$,对于所有的 $1 \le i < n$ 都有一条连接节点 $i$ 和 $i + 1$ 的边。

对于整数 $l, r(l \le r)$,我们设函数 $f(l, r)$ 表示:

  • 我们将权值在区间 $[l, r]$ 内的点保留。
  • 函数的值为新图中连通块的数量。

你需要求出如下式子的值:

$$ \sum_{l = 1} ^ n \sum_{r = l} ^ n f(l, r) $$

数据范围:$1 \le n \le 10 ^ 5$,$1 \le a_i \le n$。


Solution

我们对每个权值 $a_i$ 考虑贡献。很显然答案就是所有的 $a_i$ 可以在多少个区间 $[l, r]$ 内成为某个连通块的左端点。

对于 $a_i$,如果它要成为某个连通块的左端点,那么必然和 $i - 1$ 这个点之间没有边。现在要求的就是:有多少个权值区间 $[l, r]$ 会删除 $i - 1$ 但会保留 $i$ 这个点。

对于 $a_i, a_{i - 1}$ 分类讨论。

  • $a_{i - 1} < a_i$ 时:左端点区间为 $(a_{i - 1}, a_i]$,右端点区间为 $[a_i, n]$,故可行的区间 $[l, r]$ 有 $(a_i - a_{i - 1}) \cdot (n - a_i + 1)$ 个。
  • $a_{i - 1} > a_i$ 时:左端点区间为 $[1, a_i]$,右端点区间为 $[a_i, a_{i - 1})$,故可行的区间 $[l, r]$ 有 $(a_{i - 1} - a_i) \cdot a_i$ 个。

时间复杂度:$\mathcal O(n)$。


Code

#include <cstdio>
#include <algorithm>

const int N = 1e5 + 5;

int n, a[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] > a[i - 1]) {
            ans += 1LL * (a[i] - a[i - 1]) * (n - a[i] + 1);
        }
        if (a[i] < a[i - 1]) {
            ans += 1LL * (a[i - 1] - a[i]) * a[i];
        }
    }
    printf("%lld\n", ans);
    return 0;
}

发表评论