星座3[JOISC 2020 Day3]

发表于 分类于

题目链接

loj

题意

一个 $n\times n$ 的坐标系，每个横坐标上从小往上有一些高楼，高度为 $a_i$。有 $m$ 个星星，给出坐标及价值。现在删掉一些星星使得不存在一个平行于坐标轴的长方形，满足该长方形内有两个以上的星星，且没有高楼出现。求出最少的价值和。

$n,m\leq 10^5$

题解

补集转换，变成求出最大的价值和，使得不存在一个长方形。

考虑最高的那个高楼的 $a_i$，然后你会发现如果存在星星的纵坐标高于 $a_i$，那么最多只能有一个。

否则就会分成左右两边互不干扰的两部分。

这样就可以建出笛卡尔树，然后就可以在上面进行DP了。

设 $f_{u,i}$ 表示节点 $u$ 的子树内，保留第 $i$ 个星星的最大值。$g_u$ 表示节点 $u$ 的子树中，不保留纵坐标大于 $a_u$ 的最大值。

然后 $f_{u}$ 用线段树合并即可转移。

时间复杂度 $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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cout<<#x<<"="<<x<<endl;
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define pii pair<int,int>
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
	int x=0; char ch=getchar(); bool f=0;
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f?-x:x;
}
const int N=2e5+5;
const int M=18;
const int K=5e6+5;
namespace SGT{
	int ls[K],rs[K],rt[N],cnt;
	ll t[K];
	inline void pushtag(int u,ll d){if(u) t[u]+=d;}
	inline void pushdown(int u)
	{
		if(!u||!t[u]) return;
		pushtag(ls[u],t[u]);
		pushtag(rs[u],t[u]);
		t[u]=0;
	}
	ll ask(int u,int l,int r,int p)
	{
		if(l==r) return t[u];
		int mid=l+r>>1;
		pushdown(u);
		return p<=mid?ask(ls[u],l,mid,p):ask(rs[u],mid+1,r,p);
	}
	int merge(int x,int y)
	{
		if(!x||!y) return x+y;
		pushdown(x); pushdown(y);
		ls[x]=merge(ls[x],ls[y]);
		rs[x]=merge(rs[x],rs[y]);
		return x;
	}
	void add(int &u,int l,int r,int p,ll d)
	{
		if(!u) u=++cnt;
		if(l==r) return (void)(t[u]=max(t[u],d));
		int mid=l+r>>1;
		pushdown(u);
		p<=mid?add(ls[u],l,mid,p,d):add(rs[u],mid+1,r,p,d);
	}
}
using namespace SGT;
int n,m,q;
int f[N][M],fa[N][M],a[N],ne[N][2],Lg[N];
ll g[N];
vector<pii> s[N];
vector<int> p[N];
inline int cmp(int x,int y) {return a[x]>a[y]?x:y;}
inline int getmax(int l,int r)
{
	int k=Lg[r-l+1];
	return cmp(f[l][k],f[r-(1<<k)+1][k]);
}
int build(int l,int r)
{
	if(l>r) return 0;
	int u=getmax(l,r);
	ne[u][0]=build(l,u-1);
	if(ne[u][0]) fa[ne[u][0]][0]=u;
	ne[u][1]=build(u+1,r);
	if(ne[u][1]) fa[ne[u][1]][0]=u;
	return u;
}
void getf(int u)
{
	if(!u) return;
	fo(i,1,m) fa[u][i]=fa[fa[u][i-1]][i-1];
	fo(i,0,1) getf(ne[u][i]);
}
void dfs(int u)
{
	if(!u) return;
	fo(i,0,1) dfs(ne[u][i]);
	g[u]=g[ne[u][0]]+g[ne[u][1]];
	pushtag(rt[ne[u][0]],g[ne[u][1]]);
	pushtag(rt[ne[u][1]],g[ne[u][0]]);
	rt[u]=merge(rt[ne[u][0]],rt[ne[u][1]]);
	for(auto v:s[u]) add(rt[u],1,q,v.fi,g[u]+v.se);
	for(auto v:p[u]) g[u]=max(g[u],ask(rt[u],1,q,v));
}
int main()
{
	n=read();
	fo(i,2,n) Lg[i]=Lg[i>>1]+1;
	m=Lg[n];
	fo(i,1,n) a[i]=read(),f[i][0]=i;
	fo(j,1,m)
		fo(i,1,n-(1<<j)+1)
			f[i][j]=cmp(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	ll ans=0;
	int rt=build(1,n);
	getf(rt);
	int z,x,y,v;
	q=read();
	fo(i,1,q)
	{
		z=x=read(),y=read(),v=read();
		s[x].pb(mp(i,v));
		fd(j,m,0)
			if(fa[z][j]&&y>a[fa[z][j]])
				z=fa[z][j];
		p[z].pb(i);
		ans+=v;
	}
	dfs(rt);
	printf("%lld",ans-g[rt]);
	return 0;
}