专栏文章

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

cchenxi2009
P14567题解参与者 9已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@min2z8s3
此快照首次捕获于
2025/12/01 19:43
3 个月前
此快照最后确认于
2025/12/01 19:43
3 个月前
查看原文

思路

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

Observation 1

如果有两个合法区间相交（不算包含的情况），它们都是较劣的。
证明：这两个合法区间的交是一个合法区间。因为交在靠左的合法区间里，所以它里面的颜色在它的右边没有出现；同理在它的左边也没有出现，所以两个合法区间的交是合法区间，比这两个合法区间都要优。

Observation 2

如果有两个合法区间相互包含，较大的一个劣于较小的一个。
证明：注意到 ff 单调不降。所以较小的那个区间的每一个 vv 在放到较大的区间中向右偏移后乘上的 fi′f'_i 都不比在小区间里的 fif_i 小，对大区间价值的贡献至少有整个小区间的价值那么多。所以小区间价值一定低于包含它的大区间。
综上，我们考虑给先前的做法加上剪枝：记录已求出的最靠右的合法区间的右端点 r′r'，出现当前的 ll 在 r′r' 左侧的情况时就没有必要继续往左查了，因为此时出现相交，再往左查当前的 [l,r][l,r] 一定会被纳入到两个 Observation 中的相交靠右区间或包含较大区间的情况里，一定不优。但是这个剪枝单独作用是没有用处的，时间复杂度 O(n2)O(n^2)。
考虑记录每个右端点最终停下时的左右端点 Li,RiL_i,R_i 和下一个要检查的位置 iti\text{it}_i，我们往左扫到点 ii 的时候直接 min⁡(l,Li)→l,max⁡(r,Ri)→r\min(l,L_i)\to l,\max(r,R_i)\to r，然后继续检查 iti\text{it}_i 即可。道理很简单，从 ii 这个位置向左可以一直查到 (Li,Ri,iti)(L_i,R_i,\text{it}_i) 的状态，从包含 ii 的更大的区间出发向左也一定可以包含这个状态。
然后结束了，因为每个位置最多被 check 成功 O(1)O(1) 次，每个位置向左查最多失败一次，扫出所有可能优的合法区间的时间复杂度 O(n)O(n)。
那个单调不减的性质用到了哪里？注意到这样子做避免了两种 Observation 所述的情况，即查出来的所有区间都是互不包含互不相交的，所以它们的长度之和 ≤n\le n，我们计算答案也是 O(n)O(n) 的。没有单调不减的性质的话实际上就不能保证长度和，也就不能保证计算答案的复杂度。

代码

CPP
#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;
}
笑点解析：貌似第一步还是第二步的做法就能通过原数据了。谴责脚造数据。

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...