题解：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

即可，记录后缀和开桶维护。

CPP

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

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

文章操作

相关推荐

评论

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