[ROIR 2020 Day 1] 对常规的斗争 题解

· · 题解

下文 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，进行如下操作：

d_{2,1}\leftarrow d_{2,1}+1 d_{2,i-j+1}\leftarrow d_{2,i-j+1}-1 d_{2,n-i+1}\leftarrow d_{2,n-i+1}-1 d_{2,n-j}\leftarrow d_{2,n-j}+1

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