题解：AT_abc390_f [ABC390F] Double Sum 3

根据题目描述，可以发现

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

进行累加。

CPP

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

题解：AT_abc390_f [ABC390F] Double Sum 3

文章操作

相关推荐

评论

题解：AT_abc390_f [ABC390F] Double Sum 3