题解：AT_abc390_f [ABC390F] Double Sum 3

ZepX_D · 2025-01-26 06:50:04 · 题解

根据题目描述，可以发现 f(L,R) 其实就是 A_L,A_{L+1}\dots A_R 中的数组成的极长值域连续段数。

我们考虑扫描右端点 r，同时维护每个左端点的 f(l,r)。

每次左端点右移，那么 f(l,r) 会变成 f(l,r+1)，其实就是添加一个数 A_{r+1}，那么会造成什么影响呢？

假设 A_{r+1} 之前未出现过，那么添加之后：

• 若 A_{r+1}-1 和 A_{r+1}+1 均未出现，那么极长值域连续段数加一。
• 若出现其一，A_{r+1} 会被相邻的极长值域连续段吸收，那么极长值域连续段数不变。
• 若均出现，那么发生极长值域连续段的合并，极长值域连续段数减一。

那么我们开一个数组 pre_i 代表数字 i 上一次出现的位置，每次加入数字 x=A_{r} 时，记 a=\min(pre_{x-1},pre_{x+1}),b=\max(pre_{x-1},pre_{x+1})。

• 对于 [1,pre_{x}]，没有任何影响。
• 对于 [pre_x+1,a]，会发生 x-1 所在极长值域连续段和 x+1 所在极长值域连续段的合并，使极长值域连续段数减一。
• 对于 [a+1,b]，x 会并入x-1 所在极长值域连续段或 x+1 所在极长值域连续段，答案没有变化。
• 对于 [b+1,r]，x 不会被吸收，极长值域连续段数加一。

做法已经呼之欲出了，从左向右扫描右端点的同时维护 sum=\sum\limits_{l=1}^rf(l,r) ，同时用 ans 进行累加。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

inline LL read()
{
    LL x = 0,f = 1;char ch = getchar();
    while(!isdigit(ch)) (ch == '-') && (f = -1),ch = getchar();
    while(isdigit(ch)) x = x*10+ch-48,ch = getchar();
    return x*f;
}

const int N = 3e5+5;
int a[N],pre[N];

int main()
{
    int n = read();
    LL ans = 0,sum = 0;
    for (int i = 1;i <= n;i++)
    {
        a[i] = read();
        int x = max(pre[a[i]-1],pre[a[i]]),y = max(pre[a[i]+1],pre[a[i]]);
        if (x > y) swap(x,y);
        sum = sum+i-y-(x-pre[a[i]]),ans += sum;
        pre[a[i]] = i;
    }
    cout << ans;
    return 0;
}