题目链接：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;
}