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; }
|