题解：P14567 【MX-S12-T2】区间

· · 题解

思路

简短的线性确定性做法。

首先我们尝试找出一些合法区间。尝试固定右端点 r，显然区间 [l,r] 要盖住所有颜色为 c_r 的位置，我们先预处理出颜色 x 出现的第一个和最后一个位置 \text{mn}_x 和 \text{mx}_x，那么有 l\le\text{mn}_x\wedge r\ge\text{mx}_x，我们不妨令 l\leftarrow \text{mn}_x,r\leftarrow\text{mx}_x，然后检查 [l,r] 内出现的其他颜色，它们的 \text{mn} 和 \text{mx} 也会扩张 [l,r] 的范围。你注意到我们的前提是固定了 r，那 r 扩到右边就直接判断这个右端点没有合法区间了，每次扫到一个 l 发现成功地 check 完了 [l,r] 内的所有颜色，那么这个 [l,r] 就是合法的区间。\ 还可以注意到固定一个端点后合法区间越小价值一定越低，所以一个右端点扫到第一个合法的左端点就可以结束了。时间复杂度 O(n^2)。

然后是喜闻乐见的性质发掘环节。

Observation 1

如果有两个合法区间相交（不算包含的情况），它们都是较劣的。

证明：这两个合法区间的交是一个合法区间。因为交在靠左的合法区间里，所以它里面的颜色在它的右边没有出现；同理在它的左边也没有出现，所以两个合法区间的交是合法区间，比这两个合法区间都要优。

Observation 2

如果有两个合法区间相互包含，较大的一个劣于较小的一个。

证明：注意到 f 单调不降。所以较小的那个区间的每一个 v 在放到较大的区间中向右偏移后乘上的 f'_i 都不比在小区间里的 f_i 小，对大区间价值的贡献至少有整个小区间的价值那么多。所以小区间价值一定低于包含它的大区间。

综上，我们考虑给先前的做法加上剪枝：记录已求出的最靠右的合法区间的右端点 r'，出现当前的 l 在 r' 左侧的情况时就没有必要继续往左查了，因为此时出现相交，再往左查当前的 [l,r] 一定会被纳入到两个 Observation 中的相交靠右区间或包含较大区间的情况里，一定不优。但是这个剪枝单独作用是没有用处的，时间复杂度 O(n^2)。

考虑记录每个右端点最终停下时的左右端点 L_i,R_i 和下一个要检查的位置 \text{it}_i，我们往左扫到点 i 的时候直接 \min(l,L_i)\to l,\max(r,R_i)\to r，然后继续检查 \text{it}_i 即可。道理很简单，从 i 这个位置向左可以一直查到 (L_i,R_i,\text{it}_i) 的状态，从包含 i 的更大的区间出发向左也一定可以包含这个状态。

然后结束了，因为每个位置最多被 check 成功 O(1) 次，每个位置向左查最多失败一次，扫出所有可能优的合法区间的时间复杂度 O(n)。

那个单调不减的性质用到了哪里？注意到这样子做避免了两种 Observation 所述的情况，即查出来的所有区间都是互不包含互不相交的，所以它们的长度之和 \le n，我们计算答案也是 O(n) 的。没有单调不减的性质的话实际上就不能保证长度和，也就不能保证计算答案的复杂度。

代码

#include<bits/stdc++.h>
#define fr(a,b,c) for(int a = (b);a <= (c);a ++)
using namespace std;
const int N = 2000000;
int n,c[N],v[N],f[N],mx[N],mn[N],mxr,L[N],R[N],it[N],l,r,now;
long long ans = 1e18,sum;
int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  fr(i,1,n) cin >> c[i],mn[i] = 1e9;
  fr(i,1,n) cin >> v[i];
  fr(i,1,n) cin >> f[i];
  fr(i,1,n) mx[c[i]] = i,mn[c[i]] = min(mn[c[i]],i);//每种颜色出现最早和最晚的位置
  fr(i,1,n){//枚举右端点
    l = mn[c[i]],r = mx[c[i]],now = i - 1;//l,r 记录当前区间，now 表示下一个要检查的颜色位置
    while(r == i && now >= l){
      if(R[now] > i || L[now] <= mxr) break;//左端点和已有合法区间相交则不合法
      r = max(r,R[now]),l = min(l,L[now]),now = it[now];
    }
    if(r == i && now < l){//[l,r] 全部检查完毕，扫出了一个合法区间
      mxr = i,sum = 0;
      fr(j,l,r) sum += f[j - l + 1] * v[j];
      ans = min(ans,sum);//统计答案
    }
    else L[i] = l,R[i] = r,it[i] = now;
  }
  printf("%lld\n",ans);
  return 0;
}

笑点解析：貌似第一步还是第二步的做法就能通过原数据了。谴责脚造数据。