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

· · 题解

确定性的线性做法。

记 L_c,R_c 表示一个颜色 c 最早出现和最晚出现的位置。

由于 f 单调不降，如果存在 2 个合法区间 [l_1,r_1],[l_2,r_2] 满足 [l_2,r_2]\subset[l_1,r_1]，那就可以把 [l_1,r_1] 给扔掉。另外，容易证明如果存在 l_1\le l_2\le r_1\le r_2，[l_2,r_1] 也是合法区间。

所以对于每个左端点 l，求出最小的 r 满足 [l,r] 合法，然后把可以扔掉的区间扔掉后就只剩下一些不交的区间，这时候再计算剩下所有区间的答案即可。

扔掉区间是容易线性的，考虑怎么给 l 求出 r。从右到左扫描 l，一个显然的是 L_c<l 的 c 不能出现在 [l,r] 中。由于是从右往左扫，可以用一个单调栈维护所有不合法的位置，然后这部分要求就相当于 r<top。在满足这个后只要求 \forall c|L_c\le R,R_c\le R，可以把 R_c 看作 1，L_c 看作 -1，那只要 [l,r] 和为 0 即可，记录后缀和开桶维护。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<20,stdin),S==T)?EOF:*S++)
char B[1<<20],*S=B,*T=B;
inline int read(){
    int x=0,c=getchar();
    while(c<48) c=getchar();
    while(c>47) x=(x*10)+(c^48),c=getchar();
    return x;
}
int n,c[1000005],v[1000005],f[1000005],r[1000005],s[1000005],stk[1000005],top,lst[1000005],pre[1000005],fs[1000005],ls[1000005];
int main(){
    n=read();
    for(int i=1;i<=n;i++) c[i]=read(),fs[c[i]]=(fs[c[i]]?fs[c[i]]:i),ls[c[i]]=i;
    for(int i=1;i<=n;i++) v[i]=read();
    for(int i=1;i<=n;i++) f[i]=read();
    lst[0]=n+1;
    for(int i=n,s=0;i;i--){
        s+=(ls[c[i]]==i)-(fs[c[i]]==i),stk[++top]=i;
        while(top&&fs[c[stk[top]]]>=i) top--;
        if(lst[s]&&(!top||lst[s]<=stk[top])) r[i]=lst[s]-1;
        lst[s]=i,pre[r[i]]=i;
    }
    for(int i=2;i<=n;i++) pre[i]=max(pre[i-1],pre[i]);
    ll ans=1e18;
    for(int i=1;i<=n;i++)
        if(r[i]&&pre[r[i]]==i){
            ll res=0;
            for(int j=i;j<=r[i];j++) res+=v[j]*f[j-i+1];
            ans=min(ans,res);
        }
    cout<<ans<<'\n';
    return 0;
}