luogu P7219 [JOISC2020] 星座 3

题面传送门

实在没东西写了，随便拉一道题凑数。

首先看这个东西就感觉只和两个点有关，事实上也是这样。

关于最大值的问题肯定要把笛卡尔树建立出来，然后最大值变成两个点的LCA的权值。

根据NOID1T2那题的方法设\(f_{i,j}\)为\(i\)子树内最高的为\(j\)的最小代价，这样合并两个子树的时候可以枚举两边最高的点的高度，如果小于等于当前点权值就可以合并。

对于笛卡尔树上新增的点的问题，可以考虑，只有当前小于等于\(A_x\)的位置可以转移，而且转移之后剩下的点要加上这个权值。

容易发现上述过程可以用一个线段树合并维护，时间复杂度\(O(n\log n)\)

code:

#include<bits/stdc++.h>
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((k+1)*(x)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=2e5+5,M=N*50+5,K=2e3+5,mod=998244353,Mod=mod-1;const db eps=1e-5;const ll INF=1e18;
int L[N],R[N],A[N],st[N],H,n,m,x,y,z,Ro[N];ll g[N],F1,F2;struct Ques{int x,y;};vector<Ques> S[N];bool cmp(Ques x,Ques y){return x.x<y.x;}
namespace Tree{
	ll f[M],g[M];int L[M],R[M],cnt;void PF(int x,ll w){x&&(f[x]+=w,g[x]+=w);}void P(int v){g[v]&&(PF(L[v],g[v]),PF(R[v],g[v]),g[v]=0);}void Up(int v){f[v]=min(L[v]?f[L[v]]:INF,R[v]?f[R[v]]:INF);}
	void Ins(int x,ll y,int &v,int l=0,int r=n){!v&&(f[v=++cnt]=INF);f[v]=min(f[v],y);if(l==r) return;int m=l+r>>1;P(v);x<=m?Ins(x,y,L[v],l,m):Ins(x,y,R[v],m+1,r);}
	ll Qry(int x,int y,int &v,int l=0,int r=n){if(!v||y<l||x>r) return INF;if(x<=l&&r<=y)return f[v];int m=l+r>>1;P(v);return min(x<=m?Qry(x,y,L[v],l,m):INF,y>m?Qry(x,y,R[v],m+1,r):INF);}
	int Merge(int x,int y,int z,int l=0,int r=n){if(!x||!y) {ll G1=Qry(0,z,x,l,r),G2=Qry(0,z,y,l,r);PF(x,F2);PF(y,F1);F1=min(F1,G1);F2=min(F2,G2);return x|y;}if(l==r){l<=z&&(F1=min(F1,f[x]),F2=min(F2,f[y]));f[x]=min(f[x]+F2,f[y]+F1);return x;}P(x);P(y);int m=l+r>>1;L[x]=Merge(L[x],L[y],z,l,m);R[x]=Merge(R[x],R[y],z,m+1,r);return Up(x),x;}
	void print(int &v,int l=0,int r=n){if(!v) return;if(l==r) {printf("%d %lld\n",l,f[v]);return;}P(v);int m=l+r>>1;print(L[v],l,m);print(R[v],m+1,r);}
}
void Solve(int x){Tree::Ins(0,0,Ro[x]);int i,j;ll Ts;
	if(L[x]) {Solve(L[x]);F1=F2=INF;Ro[x]=Tree::Merge(Ro[x],Ro[L[x]],A[x]);}if(R[x]) {Solve(R[x]);F1=F2=INF;Ro[x]=Tree::Merge(Ro[x],Ro[R[x]],A[x]);}
	//printf("%d\n",x);Tree::print(Ro[x]);Pc('\n');
	if(S[x].size()) Ts=Tree::Qry(0,A[x],Ro[x]);for(Ques i:S[x]) Tree::Ins(i.x,Ts-i.y,Ro[x]);for(Ques i:S[x]) Tree::PF(Ro[x],i.y);
	//printf("%d\n",x);Tree::print(Ro[x]);Pc('\n');
}
int main(){
	freopen("1.in","r",stdin);
	int i,j;scanf("%d",&n);for(i=1;i<=n;i++) scanf("%d",&A[i]);scanf("%d",&m);while(m--) scanf("%d%d%d",&x,&y,&z),S[x].PB((Ques){y,z});
	A[0]=1e9;for(i=1;i<=n;i++) {while(A[i]>A[st[H]]) H--;L[i]=R[st[H]];R[st[H]]=i;st[++H]=i;}Solve(R[0]);printf("%lld\n",Tree::f[Ro[R[0]]]);
}