P7219 [JOISC2020] 星座 3

[JOISC2020] 星座 3

Description

https://www.luogu.com.cn/problem/P7219

HInt:如果感觉图一点性质都没有就像我一样,请考虑 $A_{X_i}<Y_i$ 。

Solution

最小的不自然度转化为最大的选中的节点的权值。

考虑一种情况,$i<j<k$,$a_i<a_j,a_k<a_j$,那么如果存在一个点 $a_i<x_d\le a_j$ ,那么点 $d$ 不会对 $[j,k]$ 之间的任何点产生影响。所以可以考虑建出大根的笛卡尔树,一个节点 $x$ 的左右子树在 $\le a_x$ 的点不会产生影响。

令 $f_{i,j}$ 表示当前在 $i$ 号点,子树中选中的点最高为 $j$。

令互不影响的两部分先计算出来,
$$
lm=\max\limits {j\le a_x} f{lson,j},rm=\max\limits_{j\le a_x} f_{rson,j}
$$
考虑两种情况:

  • 在 $x$ 位置新加入一个点,$f_{i,x_i}=\max c_x+lm+rm$
  • $x$ 位置不加入新点,$f_{i,j}=\max{f_{lson,j}+rm,lm+f_{rson,j}}$

这样状态数是 $n^2$ 的,但由于点只有 $m$ 个,显然有效状态没有这么多。我们不妨钦定选中的点最高为 $j$ 且一定要选中。

第一种转移为单点修改取 $\max$,第二种转移为区间加,合并取 $\max$。考虑线段树合并。

复杂度 $O(m\log n)$。

upt 2023.11.17 : 感觉线段树合并推懒标记的复杂度是不是错的啊。用标记永久化的复杂度是对的。

Code

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
#define int long long
#define maxn 200005
struct yyy{
int ls,rs,lazy,Max;
}f[maxn*20];
int n,m,root[maxn],cnt;
inline void Pushup(int rt) {
f[rt].Max=max(f[f[rt].ls].Max,f[f[rt].rs].Max);
}
inline void Pushdown(int rt) {
if (f[rt].lazy) {
int k=f[rt].lazy;f[rt].lazy=0;
if (f[rt].ls) f[f[rt].ls].lazy+=k,f[f[rt].ls].Max+=k;
if (f[rt].rs) f[f[rt].rs].lazy+=k,f[f[rt].rs].Max+=k;
}
}
inline void Update(int l,int r,int &rt,int head,int k) {
if (!rt) rt=++cnt,f[rt].Max=0;
if (l==r) return f[rt].Max=max(f[rt].Max,k),void();
Pushdown(rt);
int mid=l+r>>1;
if (head<=mid) Update(l,mid,f[rt].ls,head,k);
else Update(mid+1,r,f[rt].rs,head,k);
Pushup(rt);
}
const int inf=1e9;
inline int Query(int l,int r,int rt,int head,int tail) {
if (!rt) return 0;
if (head<=l&&r<=tail) return f[rt].Max;
Pushdown(rt);
int mid=l+r>>1,tmp1=0,tmp2=0;
if (head<=mid) tmp1=Query(l,mid,f[rt].ls,head,tail);
if (tail>mid) tmp2=Query(mid+1,r,f[rt].rs,head,tail);
return max(tmp1,tmp2);
}
int sum1,sum2;
inline void merge(int l,int r,int &x,int y) {
if (!x||!y) {
if (!x&&!y) x=0;
else if (!x) x=y,f[x].Max+=sum1,f[x].lazy+=sum1;
else f[x].Max+=sum2,f[x].lazy+=sum2;
return ;
}
int mid=l+r>>1;
if (l==r) {
if (f[x].Max+sum2>f[y].Max+sum1) f[x].Max+=sum2,f[x].lazy+=sum2;
else x=y,f[x].Max+=sum1,f[x].lazy+=sum1;
return ;
}
Pushdown(x);Pushdown(y);
merge(l,mid,f[x].ls,f[y].ls);
merge(mid+1,r,f[x].rs,f[y].rs);
Pushup(x);
}
int a[maxn];
vector<pair<int,int> >O[maxn];
int ls[maxn],rs[maxn],stac[maxn],tot;
inline void solve(int x,int L,int R) {
int tmp1=0,tmp2=0;
if (ls[x]&&rs[x]) {
solve(ls[x],L,x-1);
solve(rs[x],x+1,R);
tmp1=sum1=Query(1,n,root[ls[x]],1,a[x]);
tmp2=sum2=Query(1,n,root[rs[x]],1,a[x]);
merge(1,n,root[ls[x]],root[rs[x]]);
root[x]=root[ls[x]];
}
else if (ls[x]) {
solve(ls[x],L,x-1);
tmp2=0;tmp1=Query(1,n,root[ls[x]],1,a[x]);
root[x]=root[ls[x]];
}
else if (rs[x]) {
solve(rs[x],x+1,R);
tmp1=0;tmp2=Query(1,n,root[rs[x]],1,a[x]);
root[x]=root[rs[x]];
}

for (auto tmp:O[x]) Update(1,n,root[x],tmp.fi,tmp.se+tmp1+tmp2);
}
signed main(void){
int i,x,y,c,ans=0;
read(n);
for (i=1;i<=n;i++) read(a[i]);
for (i=1;i<=n;i++) {
while (tot&&a[stac[tot]]<a[i]) ls[i]=stac[tot],tot--;
rs[stac[tot]]=i,stac[++tot]=i;
}
read(m);
for (i=1;i<=m;i++) {
read(x);read(y);read(c);ans+=c;
O[x].push_back(mk(y,c));
}
solve(stac[1],1,n);
printf("%lld",ans-f[root[stac[1]]].Max);
return 0;
}