「JOISC 2020 Day3」星座 3 (dp)

考虑根据$A_i$的值建立笛卡尔树，此时平面被划分为个矩形空间

下称选择一个点为保留一个星星

Snipaste_2021-03-13_11-21-27.png

具体的，对于笛卡尔树上的节点$(u,l,r)$，它的矩形就是父节点矩形以下，且满足$x\in[l,r],y>A_u$的部分

可以用一个线段树来查询矩形内部的点，线段树上每个节点维护$y_{max}$，每次剥掉$y_{max}>A_u$的部分

复杂度为均摊$O(n\log n)$

观察笛卡尔树的树形，容易发现，

1.笛卡尔树左右子树的矩形之间不会产生贡献

2.每个节点对应的矩形区间内最多选择一个点

3.如果一个节点$(u,l,r)$的祖先中有一个$x_i\in[l,r]$的点选择了，那么自己的矩形内不能选择点

那么令$dp_{u,i}$表示父节点传下来的点$x=i$时，$u$子树内的答案

对于$i\in[l,r]$的情况，可以直接将儿子的值合并，加上自己区间内部的权值总和$C_i$

对于$i\not \in[l,r]$的情况，这一部分答案相同

可以从自己子区间内选择一个点$(x_i,y_i,c_i)$下传，此时沿用上面合并得到的$dp$值

$outans=\min\{dp_{x_i}+sum-c_i\}$

如何实现这个奇怪的$dp$过程？

考虑子树的区间不交，因此对于$(u,l,r)$，只维护$l,r$内部的答案，对于$i\not \in[l,r]$的部分额外记录一个值$dp_u$

考虑用一棵静态的线段树维护$dp$，线段树上存储$i\in[l,r]$的答案

合并左右儿子时，两个儿子的区间不交

因此，实际上答案就是将$dp_{ls}$加到$[u,r]$上，将$dp_{rs}$加到$[l,u]$上

处理出$sum$之后，区间修改$[l,r]$的答案，对于$dp_u$直接按照上面的方法枚举$(x_i,y_i,c_i)$来计算即可

复杂度为$O(n\log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
int n,A[N];
struct SegFinder{
	vector <Pii> V[N];
	int s[N<<2];
	void Build(int p,int l,int r){
		if(l==r) {
			sort(V[l].begin(),V[l].end());
			s[p]=V[l].empty()?0:V[l].back().first;
			return;
		}
		int mid=(l+r)>>1;
		Build(p<<1,l,mid),Build(p<<1|1,mid+1,r);
		s[p]=max(s[p<<1],s[p<<1|1]);
	}
	void Get(int p,int l,int r,int ql,int qr,int x,vector <Pii> &Res){
		if(s[p]<x) return;
		if(l==r) {
			while(!V[l].empty() && V[l].back().first>=x) Res.pb(mp(l,V[l].back().second)),V[l].pop_back();
			s[p]=V[l].empty()?0:V[l].back().first;
			return;
		}
		int mid=(l+r)>>1;
		if(ql<=mid) Get(p<<1,l,mid,ql,qr,x,Res);
		if(qr>mid) Get(p<<1|1,mid+1,r,ql,qr,x,Res);
		s[p]=max(s[p<<1],s[p<<1|1]);
	}
} Finder;

int ls[N],rs[N],stk[N],top,mk[N];
int rt[N];
ll dp[N],s[N<<2],t[N<<2];
ll Que(int p,int l,int r,int ql,int qr){
	if(ql<=l && r<=qr) return s[p];
	int mid=(l+r)>>1; ll res=1e18;
	if(ql<=mid) cmin(res,Que(p<<1,l,mid,ql,qr));
	if(qr>mid) cmin(res,Que(p<<1|1,mid+1,r,ql,qr));
	return res+t[p];
}

void Upd(int p,int l,int r,int ql,int qr,ll x){
	if(ql<=l && r<=qr) {
		s[p]+=x,t[p]+=x;
		return;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) Upd(p<<1,l,mid,ql,qr,x);
	if(qr>mid) Upd(p<<1|1,mid+1,r,ql,qr,x);
	s[p]=min(s[p<<1],s[p<<1|1])+t[p];
}

// 线段树内存储的是 如果父节点有下传下来的答案
// dp 存储没有父节点下传的答案

void Solve(int p,int l,int r){
	vector <Pii> V; Finder.Get(1,1,n,l,r,A[p]+1,V);
	// 拿出我的决策矩形

	if(l<p) Solve(ls[p],l,p-1);
	if(p<r) Solve(rs[p],p+1,r);
	if(rs[p]) Upd(1,1,n,l,p,dp[rs[p]]);
	if(ls[p]) Upd(1,1,n,p,r,dp[ls[p]]);
	ll sum=0;
	for(Pii i:V) sum+=i.second;
	if(sum) Upd(1,1,n,l,r,sum); 
	// 如果父节点有下传，那么自己必须被清空
	// 否则考虑选择一个下传下去，这样就能得到 没有父节点下传时的值
	dp[p]=Que(1,1,n,l,r);
	for(Pii i:V) cmin(dp[p],Que(1,1,n,i.first,i.first)-i.second);
}

int main(){
	n=rd();
	rep(i,1,n) {
		A[i]=rd();
		while(top && A[stk[top]]<=A[i]) ls[i]=stk[top--];
		stk[++top]=i;
	}
	top=0;
	drep(i,n,1) {
		while(top && A[stk[top]]<A[i]) rs[i]=stk[top--];
		stk[++top]=i;
	}
	rep(i,1,n) mk[ls[i]]=mk[rs[i]]=1;
	rep(_,1,rd()) {
		int x=rd(),y=rd(),c=rd();
		Finder.V[x].pb(mp(y,c));
	}
	Finder.Build(1,1,n);
	rep(i,1,n) if(!mk[i]) {
		Solve(i,1,n);
		printf("%lld\n",dp[i]);
		return 0;
	}
}