P14567区间

题意简述

每一个位置有一个权值，一个颜色，整个序列有一个代价序列，我们要找到价值最小的合法区间。定义合法的区间为区间内所有出现过的颜色，所有这个颜色的下标都出现在这个区间里。

思路解释

我们假设找到了所有合法的区间，因为代价序列

f

单调不减，那我们找到的合法区间一定越短越好。然后我们在看特殊性质给了一个

c_i\le5

的性质，那我们可以想到从颜色上入手。

对于每一个颜色，我们一定要把这个颜色的最左边和最右边框进去‘
对于一个区间中的每一个元素，它的左右端点一定都存在于这个区间中

我们要找到较短的合法区间，那我们先想到暴力枚举左端点，直接往右扩展右端点，不难发现在这种情况下，如果颜色比较稀疏的情况下，每一个区间维护的长度就会尽量的短。

这边再给出一个性质，就是对于每一个点向右扩展的最小合法区间，一定是重合或独立，因此一定不会相交，结合合法区间的定义不难证明，如果两个区间存在相交的部分，那在不相交的部分一定存在相同的颜色，否则可以被分割成三个独立的区间。

在上述过程中，检验区间合法只需要判断这个区间中任何一个点的颜色最左端出现的位置是否在这个区间外即可，如果右端点比当前这个颜色的最右端要小，直接把右端点扩展到这个颜色的最右端位置。

复杂度分析

首先对于可能的左端点，只有颜色值域的个数，因为如果一个点要成为左端点，他一定得是这个颜色第一次出现的位置。

对于这个区间内出现的位置，这个位置的颜色的左右端点一定被这个区间覆盖，在颜色种类并不多的时候，每个位置最多被所有颜色扫到一次，而在颜色种类较多的时候，每个端点能够扩展出去的区间长度也会相应减少，又因为每个区间要么独立要么包含，基本是一个小常数的线性复杂度。在最后整理答案的时候直接取最小值，我们可能可以做到近似线性，笔者在考试时求最优区间答案的时候用一个堆维护，最劣的情况是每一个点都是独立的合法区间，最多会在堆中插入

n

个元素

因此复杂度瓶颈应该是堆的部分，复杂度

O(n \log n)

。

具体实现

CPP

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;
int le[1000005],ri[1000005];
ll c[1000005],v[1000005],f[1000005];
priority_queue<ll,vector<ll>,greater<ll>> Q;
inline ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
bool flag;
int main()
{
	//freopen("interval.in","r",stdin);
	//freopen("interval.out","w",stdout);
	int n;
	//cin>>n;
	n=read();
	for(int i=1;i<=n;i++) le[i]=1e9;
	for(int i=1;i<=n;i++)
	{
		//cin>>c[i];
		c[i]=read();
		le[c[i]]=min(le[c[i]],i);
		ri[c[i]]=max(ri[c[i]],i);
	}
	for(int i=1;i<=n;i++) v[i]=read();//cin>>v[i];
	for(int i=1;i<=n;i++) f[i]=read();//cin>>f[i];
	for(int i=1;i<=n;i++)
	{
		int l=i,r=ri[c[i]];
		if(l>le[c[i]]) continue;
		int pos=l+1;
		flag=1;
		while(pos<=r)
		{
			if(le[c[pos]]<l)
			{
				flag=0;
				break;
			}
			r=max(r,ri[c[pos]]);
			pos++;
		}
		if(!flag) continue;
		ll ans=0;
		for(int j=l;j<=r;j++)
		{
			ans+=(v[j]*f[j-l+1]);
		}
		Q.push(ans);
	}
	cout<<Q.top();
	return 0;
}

后记

这份代码在在不开O2不加优化的时候大概是

1.8s

，加上快读可以来到

400ms

，对于复杂度的证明不一定十分准确，欢迎大家讨论代码复杂度或构造可以让这个代码运行时间尽可能久的数据。

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

文章操作