自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:51:49，当前版本为作者最后更新于2023-10-24 15:56:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

下文 $a$ 数组下标默认从 $0$ 开始。

钦定只有在一个连续子段中第一个出现的某种数才会做出贡献。于是有一种比较简单的想法：枚举每一个数 $a_i$，如果存在 $j<i$ 使得 $a_j=a_i$，那么 $a_i$ 可以做出贡献的区间的左端点 $l$ 必然满足 $j<l\le i$。这是假设确定了这个 $l$，那么 $a_i$ 对长度在 $[i-l+1,n-l]$ 之间的区间都各有一个贡献，区间加可以用差分数组维护。时间复杂度 $O(n^2)$，可以过 $n\le 5000$ 的部分分。

考虑优化上面的维护过程：对于每个 $l$，实际上相当于差分数组 $d_{1,i-l+1}\leftarrow d_{1,i-l+1}+1$，$d_{n-l+1}\leftarrow d_{n-l+1}-1$。因为 $l$ 的取值是连续的一段 $(j,i]$，所以建出 $d$ 的二阶差分数组 $d_2$。现在只需对于每个 $i$，找到对应的 $j$，进行如下操作：

用 std::map 维护一个数上一次出现的位置，时间复杂度 $O(n\log n)$。最后做两遍前缀和将答案数组还原即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n; cin>>n;
  vector<int> a(n);
  vector<long long> s(n+3);
  for(auto &i:a)cin>>i;
  map<int,int> m;
  for(int i=0;i<n;i++){
    int x=m.count(a[i])?m[a[i]]:-1;
    s[1]++,s[i-x+1]--,s[n-i+1]--,s[n-x+1]++;
    m[a[i]]=i;
  } // 对二阶差分数组进行操作
  partial_sum(s.begin(),s.end(),s.begin());
  partial_sum(s.begin(),s.end(),s.begin());
  for(int i=1;i<=n;i++)cout<<s[i]<<' ';
  cout<<endl;
  return 0;
}