T1

原题链接

对于区间 \([l,r]\) ，答案是 \(max(cntr,cntl)-x\) （其中 \(cntl,cntr\) 分别表示区间内左括号和右括号的数量， \(x\) 表示匹配的括号数量）。

首先考虑 \(max(cntr,cntl)\) 。该柿子可以转化成 \((cntl+cntr+|cntr-cntl|)/2\) 。前面的 \(cntl+cntr\) 非常好算，就是 \(\sum_{i=1}^n i*(n-i+1)\) 。后面带绝对值的柿子怎么算呢？可以令 \(1\) 表示左括号， \(-1\) 表示右括号，求一个前缀和。然后将前缀和从小到大排序。对于排序后的前缀和 \(sum[i]\) ，它对答案的贡献是 \(i\times sum[i]-\sum_{j=0}^{j-1}sum[j]\) 。最后别忘了除以 \(2\) 。

再考虑 \(x\) 。我们用栈模拟匹配过程，如果发现一对匹配的括号（用 \(posl\) 表示左括号的位置， \(posr\) 表示右括号的位置），那么它会在 \((n-posr+1)\times posl\) 个区间中出现。那么它对答案的贡献就是 \(-(n-posr+1)\times posl\) 。

这样就可以在 \(O(n)\) 的复杂度内求得答案。

\(code:\)

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
long long n,t,s[200005],stk[200005],r,ans;char a[200005];
int main(){
	freopen("common.in","r",stdin);
	freopen("common.out","w",stdout);
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%s",&n,a);
		ans=0;s[0]=0;
		for(int i=1;i<=n;++i)
			ans+=i*(n-i+1);
		for(int i=1;i<=n;++i){
			if(a[i-1]=='(') s[i]=s[i-1]+1;
			else s[i]=s[i-1]-1;
		}
		sort(s,s+n+1);
		long long sum=0;
		for(int i=0;i<=n;++i){
			ans+=s[i]*i-sum;
			sum+=s[i];
		}//cout<<ans<<endl;
		ans/=2;
		r=0;
		for(int i=0;i<n;++i){
			if(a[i]=='(')
				stk[++r]=i+1;
			else if(r>0){
				ans-=(n-i)*stk[r];//stk[r]~i+1
				--r;
			}
		}
		printf("%lld\n",ans);
	}
	fclose(stdin);fclose(stdout); 
	return 0;
}

T3

原题链接

首先有一个性质，任意两个三角形没有公共的部分，因为如果有公共部分一定不如把它们合起来更优。

然后就可以考虑 \(dp\) 。设 \(f[i]\) 表示考虑了 \(x\) 坐标在 \([0,i]\) 内的所有点，存在一个右下角的横坐标为 \(i\) 的三角形时的最小代价。枚举上一个三角形的结束位置，则状态转移方程为：

\(f[i]=min_{j<i}(f[j]+(i-j-1)\times A+cost)\)

其中， \(cost\) 为所有满足 \(j<x<=i,1<=y<k-i\) 的点的 \(c\) 之和。

然后用线段树维护即可。

\(code:\)

#include<iostream>
#include<vector>
#include<cstdio>
#define ll long long
using namespace std;
ll n,k,A,ans,x,y,z,cnt[200005],f[200005];
struct node{
	int l,r;ll minn,lazy;
} p[800005];
struct node2{
	int x;ll w;
};vector <node2> a[200005];
void build(int u,int l,int r){
	p[u].l=l;p[u].r=r;
	if(l==r)
		return ;
	int mid=(l+r)>>1;
	build(u<<1,l,mid);build(u<<1|1,mid+1,r);
}
void push_down(int u){
	p[u<<1].minn+=p[u].lazy;
	p[u<<1|1].minn+=p[u].lazy;
	p[u<<1].lazy+=p[u].lazy;
	p[u<<1|1].lazy+=p[u].lazy;
	p[u].lazy=0;
}
void add(int u,int l,int r,ll w){
	if(p[u].l>=l&&p[u].r<=r){
		p[u].minn+=w;p[u].lazy+=w;
		return ;
	}
	push_down(u);
	int mid=(p[u].l+p[u].r)>>1;
	if(mid>=l)
		add(u<<1,l,r,w);
	if(mid<r)
		add(u<<1|1,l,r,w);
	p[u].minn=min(p[u<<1].minn,p[u<<1|1].minn); 
}
ll ask(int u,int l,int r){
	if(p[u].l>=l&&p[u].r<=r)
		return p[u].minn;
	push_down(u);
	int mid=(p[u].l+p[u].r)>>1;ll re=1e18;
	if(mid>=l)
		re=min(re,ask(u<<1,l,r));
	if(mid<r)
		re=min(re,ask(u<<1|1,l,r));
	return re;
}
int main(){
	ans=1e18;
	scanf("%lld%lld%lld",&n,&k,&A);
	build(1,1,k+2);
	for(int i=1;i<=n;++i){
		scanf("%lld%lld%lld",&x,&y,&z);
		a[y].push_back((node2){x,z});
		if(x+y!=k)
			cnt[x]+=z;
	}
	for(int i=0;i<=k;++i){
		for(int j=0;j<a[k-i].size();++j)
			add(1,1,a[k-i][j].x+1,-a[k-i][j].w);
		add(1,1,i+1,cnt[i]);
		if(i!=0)
			add(1,1,i,A);
		f[i]=ask(1,1,i+1);
		add(1,i+2,i+2,f[i]);
	}
	printf("%lld\n",f[k]);
	fclose(stdin);fclose(stdout);
	return 0;
}