CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!) E.Bracket Cost(思维题/合法栈序列的性质&单调栈)

题目

对于一个括号序列，可以执行两种操作：

1. 选择它的一个子串，并且将它循环右移一位，例如，"(())"循环右移后将会变为")(()"

2. 在任何位置插入一个左括号或右括号

定义一个括号序列的代价，为使其变为合法括号序列的最小操作次数

给定长度为n(n<=2e5)的括号序列，其有n(n+1)/2个子串，求其所有子串的代价之和

实际t(t<=1e5)组样例，但sumn不超过2e5

思路来源

https://www.cnblogs.com/came11ia/p/16919478.html

uoj群

题解

感觉是栈的一个显著性质，典中典

经典套路，初始值为0，将(看做是+1，)看做是-1，做前缀和

如，对于)(()))来说，就是0 -1 0 1 0 1 2，记该数组为a，

因为这个序列曾从0到-1，所以-1左侧需要补至少一个左括号（说明至少有一个右括号不匹配），

不妨贪心地，将这一个左括号补在序列的最左侧，

而-1到2在补了这一个左括号之后，变为从0到3，此时多了3个左括号

此时在序列最右侧还需要补3个右括号

归纳一下，

需要补的左括号数（不匹配的右括号数）为a[l]-min(a[l],...,a[r])①

需要补的右括号数（不匹配的左括号数）为a[r]-min(a[l],...,a[r])②

如果只有第二种操作，答案就是①+②，

但是，有了第一种操作之后，答案就是max(①,②)，

因为，当①、②同时大于0时，表明同时有不匹配的左、右括号，

而循环移位某个子串，总能将形如)xxxx(的串，移位(xxxx)，从而减少一对不匹配的左右括号

所以，最终答案是①+②-min(①,②)，即max(①,②)

另一种理解方式，是将a数组化成折线图，然后发现，

当a[l]和a[r]不等时，只能通过补左/右括号的方式使二者相同，需要abs(a[l]-a[r])的代价，

a[l]和a[r]相同后，如果min(a[l],...,a[r])还比a[r]小，记最后一个值为min(a[l],...,a[r])的位置为x，

则(x,r]间总有左括号，总可以通过循环移位的方式，使min(a[l],...,a[r])+1，

最终，使min(a[l],...,a[r])和a[r]拉齐

所以，最终的答案就是(max(a[l],a[r])-min(a[l],a[r]))+(min(a[l],a[r])-min(a[l],...,a[r]))

第一部分表示将左右端点拉齐，第二部分表示将右端点和[l,r]区间最小值拉齐

即最终答案为max(a[l],a[r])-min(a[l],...a[r])，

注意到a数组上的[l,r]，实际对应字符串的[l+1,r]，所以需要l<r，即>=2长度区间才有贡献，

max(a[l],a[r])将数组sort一下即可统计每个位置作为最大值的贡献，

值域在[-n,n]之间，用基数排序也可以O(n)的完成这个统计

而区间最小值min(a[l],...a[r])，用单调栈维护一下，朴素应用，注意不算长度=1的区间产生的贡献

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
int t,n,a[N],b[N],stk[N];
char s[N];
int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%s",&n,s+1);
		int v=0,c=0;
		a[0]=b[0]=0;
		stk[++c]=0;
		vector<int>l(n+1,-1),r(n+1,n+1);
		for(int i=1;i<=n;++i){
			v+=(s[i]=='('?1:-1);
			a[i]=v;
			b[i]=a[i];
			while(c && a[stk[c]]>a[i]){
				r[stk[c]]=i;
				c--;
			}
			if(c)l[i]=stk[c];
			stk[++c]=i;
		}
		sort(b,b+n+1);
		ll ans=0;
		for(int i=0;i<=n;++i){
			ans+=1ll*i*b[i];
			ans-=1ll*(i-l[i])*(r[i]-i)*a[i];
			ans+=a[i];
		}
		printf("%lld\n",ans);
	}
	return 0;
}