基于单调栈的做法：

先观察题意，发现

f_i

是单调不减的，所以有：

结论

若合法区间

[L,R]

包含但不等于合法区间

[l,r]

，那我们一定会将

[l,r]

作为答案区间。

再根据题目中对合法区间的定义，自然而然的想到我们去记录每种数字出现的最左和最右的位置。

然后我们发现最后的答案区间一定是这些区间中某一些的补集，所以我们可以先对左端点进行排序，这样只用考虑右端点的数据的处理。

这里我们对右端点维护一个单调栈，然后这个时候有两种情况，一种是下一个进入的区间与栈顶的区间没有交点，一种有交点。

对于有交点的情况，我们发现，这种情况下两个区间一定“连锁”，即选了一个就一定选中另外一个。所以，我们可以直接将两个区间“合并为一个区间”。

在这就是没有交点时，这种情况说明我们栈里边已经存下了以栈顶区间所代表的颜色为开头的合法区间的信息，直接弹栈就行（细节下下一段写）。

这样对于上上段的细节就会好处理许多，直接取栈顶的区间，就是答案区间，统计即可。

写到这里，聪明的同学已经发现了问题，我们上面维护的区间是丢失了中间信息的区间，我们不知道一个栈顶区间有没有栈里其他区间代表的颜色的点。所以我们维护每个区间中该种颜色点的数量，合并区间的时候进行累加。最后只需要判断区间长与总点数是否相等即可。

注意

当这样一组数据

MARKDOWN

7
1 2 3 1 3 2 1
1 2 4 8 16 32 64
1 1 1 1 1 1 1

出现的时候，我们的栈无法弹出，也无法计算答案，所以最后要进行特判

时间复杂度瓶颈在排序,

O(nlogn)

#25 89ms

code:

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e6 + 20;
const int INF = 1e9;
const ll INFF = 1e18;

int read(){
	int 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<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}

int n;
int c[N], v[N], f[N];
struct color{
	int l, r, w;
}col[N];
bool cmp( color A , color B ){return A.l < B.l;}
int stk[N], top;
ll ans = INFF;
int main(){
	freopen("interval6.in","r",stdin);
//	freopen("interval.out","w",stdout);
	n = read();
	for( int i = 1 ; i <= n ; ++i )col[i].l = col[i].r = INF; 
	for( int i = 1 ; i <= n ; ++i ){
		c[i] = read();
		col[c[i]].w++;
		if( col[c[i]].l == INF )col[c[i]].l = col[c[i]].r = i;
		col[c[i]].r = max(col[c[i]].r,i);
	}
	for( int i = 1 ; i <= n ; ++i )v[i] = read();
	for( int i = 1 ; i <= n ; ++i )f[i] = read();
	sort(col+1,col+n+1,cmp);
	for( int i = 1 ; i <= n ; ++i ){
		if( col[i].l > col[stk[top]].r && top ){
			int lc = col[stk[top]].l, rc = col[stk[top]].r;
			if( col[stk[top]].w == rc - lc + 1 ){
				ll tmp = 0;
				for( int j = lc ; j <= rc ; ++j )tmp += v[j] * f[j - lc + 1];
				ans = min(ans, tmp);
				top--;
			}
		}
		if( col[i].l == INF )break; 
		while( col[stk[top]].r < col[i].r && top ){
			if( col[i].l <= col[stk[top]].r ){
				col[i].l = min(col[i].l,col[stk[top]].l);
				col[i].r = max(col[i].r,col[stk[top]].r);
				col[i].w += col[stk[top]].w;
			}
			top--;
		}
		stk[++top] = i;
	}
	int lmin = INF, rmax = 0, tot = 0;
	while( top > 0 ){
		lmin = min(lmin,col[stk[top]].l);
		rmax = max(rmax,col[stk[top]].r);
		tot += col[stk[top--]].w;
		if( col[stk[top]].r < lmin ){
			ll tmp = 0;
			for( int i = lmin ; i <= rmax ; ++i )tmp += f[i - lmin + 1] * v[i];
			ans = min(ans,tmp);
			lmin = INF, rmax = 0, tot = 0;
		}
	}
	cout << ans << "\n";
	return 0;
}

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

文章操作

基于单调栈的做法：

相关推荐

评论

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