笛卡尔树好神奇啊！
我们考虑对白色区域维护以最大值为中点笛卡尔树，然后考虑怎么合并左右区间：
令 $f[h]$ 表示最高高度为 $h$ 的最大保留权和，v 表示当前笛卡尔树节点的权值.
考虑如何合并左右区间：
显然，如果要将 $f[y]$ 贡献给 $f[x]$，那么 $x$ 要大于 $y.$
我们将左右区间的所有状态分成大于等于 $v$ 和小于等于 $v$.
因为要求任意不包含白点的矩阵只能有一个星星，所以左面小于等于 $v$ 的可以完全贡献给右面大于等于 $v$ 的（左面大于 $v$ 的贡献不了）
这个在线段树上就是一个区间标记下传.
然后对于小于 $v$ 的情况比较难处理，但是我们发现笛卡尔树中父亲的权值大于等于当前权值，所以小于 $v$ 的所有情况只保留一个就行（既左max+右max 赋给 $f[v-1]$)
然后来一个线段树合并合并一下状态就行.
code:
#include <bits/stdc++.h>
#define N 200007
#define ll long long
#define lson s[x].ls
#define rson s[x].rs
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
int tot,n,top;
int ch[N][2],a[N],val[N],sta[N],size[N],RT[N];
int newnode() { return ++tot; }
struct data { int h,c; data(int h=0,int c=0):h(h),c(c){} };
struct node { int ls,rs;ll ma,ad; }s[N*80];
vector<data>ge[N];
void mark(int x,ll v) { s[x].ma+=v,s[x].ad+=v; }
void pushdown(int x)
{
if(s[x].ad)
{
if(lson) mark(lson,s[x].ad);
if(rson) mark(rson,s[x].ad);
s[x].ad=0;
}
}
void update(int &x,int l,int r,int p,ll v)
{
if(!x) x=newnode();
s[x].ma=max(s[x].ma,v);
if(l==r) return;
int mid=(l+r)>>1;
pushdown(x);
if(p<=mid) update(lson,l,mid,p,v);
else update(rson,mid+1,r,p,v);
}
ll query(int x,int l,int r,int L,int R)
{
if(!x) return 0;
if(l>=L&&r<=R) return s[x].ma;
pushdown(x);
int mid=(l+r)>>1; ll re=0;
if(L<=mid) re=max(re,query(lson,l,mid,L,R));
if(R>mid) re=max(re,query(rson,mid+1,r,L,R));
return re;
}
void addv(int x,int l,int r,int L,int R,ll v)
{
if(!x) return;
if(l>=L&&r<=R) { mark(x,v); return; }
pushdown(x);
int mid=(l+r)>>1;
if(L<=mid) addv(lson,l,mid,L,R,v);
if(R>mid) addv(rson,mid+1,r,L,R,v);
s[x].ma=max(s[lson].ma,s[rson].ma);
}
int merge(int x,int y)
{
if(!x||!y) return x+y;
pushdown(x),pushdown(y);
int now=newnode();
s[now].ma=max(s[x].ma,s[y].ma);
s[now].ls=merge(s[x].ls,s[y].ls);
s[now].rs=merge(s[x].rs,s[y].rs);
return now;
}
void dfs(int x)
{
size[x]=1;
if(ch[x][0]) dfs(ch[x][0]),size[x]+=size[ch[x][0]];
if(ch[x][1]) dfs(ch[x][1]),size[x]+=size[ch[x][1]];
}
void mer(int x,int y,int tmp)
{
ll a=query(RT[x],0,n,0,tmp);
ll b=query(RT[y],0,n,0,tmp);
addv(RT[x],0,n,tmp,n,b);
addv(RT[y],0,n,tmp,n,a);
ll c=query(RT[x],0,n,0,tmp-1);
ll d=query(RT[y],0,n,0,tmp-1);
update(RT[x],0,n,tmp-1,c+d);
RT[y]=merge(RT[x],RT[y]);
}
void solve(int x)
{
for(int i=0;i<ge[x].size();++i)
update(RT[x],0,n,ge[x][i].h,ge[x][i].c);
if(ch[x][0])
solve(ch[x][0]),mer(ch[x][0],x,a[x]);
if(ch[x][1])
solve(ch[x][1]),mer(ch[x][1],x,a[x]);
}
int main()
{
// setIO("input");
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
for(int i=1;i<=n;++i)
{
while(top&&a[i]>=a[sta[top]])
ch[i][0]=sta[top],--top;
if(top) ch[sta[top]][1]=i;
sta[++top]=i;
}
int rt=sta[1],m;
ll t=0;
scanf("%d",&m);
for(int i=1;i<=m;++i)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
ge[x].push_back(data(y,c));
t+=(ll)c;
}
dfs(rt);
solve(rt);
printf("%lld
",t-query(RT[rt],0,n,0,n));
return 0;
}