「JOISC 2020 Day3」星座 3 （DFS序）（笛卡尔树）（DP）

本文主要是介绍「JOISC 2020 Day3」星座 3 （DFS序）（笛卡尔树）（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

建出笛卡尔树，假设当前处理 $[l, r]$ ，高于最大值的星星只能保留一个
一颗星星可以定位到上述的唯一一个区间，所以我们可以枚举这一棵星星
选了这颗星星的话会 $b a n$ 掉一些区间的星星，而这个在笛卡尔树上是一条链
如果令 $f, g$ 表示当前区间不选 / 选星星，那么 $b a n$ 掉的就是强制不选星星
于是我们维护插值， $d f s$ + 树状数组维护

#include<bits/stdc++.h>
#define cs const
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
cs int N = 2e5 + 50;
int read(){int cnt=0, f=1; char ch=0;while(!isdigit(ch)){ ch=getchar(); if(ch=='-') f=-1; }while(isdigit(ch)) cnt=cnt*10+(ch-'0'), ch=getchar();return cnt*f;
}
int n, a[N], m, lg[N];
int mn[20][N], fa[N], ch[N][2], nd;
int ps[N]; map<pi,int> mp;
int chk(int i, int j){ return a[i] > a[j] ? i : j; }
struct star{ int x, y, c; } o[N];
vector<pi> G[N];
int RMQ(int l, int r){int x=lg[r-l+1];return chk(mn[x][l],mn[x][r-(1<<x)+1]);
}
namespace SGT{int tag[N<<2]; #define mid ((l+r)>>1)void modify(int x, int l, int r, int p, int v){if(r<=p){ tag[x]=v; return; }modify(x<<1,l,mid,p,v); if(p>mid) modify(x<<1|1,mid+1,r,p,v);}int qry(int x, int l, int r, int p){if(l==r) return tag[x]; int as = tag[x];if(p<=mid) as=max(as,qry(x<<1,l,mid,p));else as=max(as,qry(x<<1|1,mid+1,r,p)); return as;}
}
cs ll INF = 1e18;
int build(int l, int r){if(l>r) return 0;int x = ++nd, p = RMQ(l,r); ps[p]=mp[pi(l,r)]=x;ch[x][0]=build(l,p-1);ch[x][1]=build(p+1,r); fa[ch[x][0]]=fa[ch[x][1]]=x; return x;	
}
int in[N], out[N], sgn;
void dfs(int u){ if(!u) return; in[u]=++sgn; dfs(ch[u][0]); dfs(ch[u][1]); out[u]=sgn; }
namespace dlt{ll c[N];void add(int x, ll v){ for(;x<=n;x+=x&-x) c[x]+=v; }ll qry(int x){ ll as=0; for(;x;x-=x&-x) as+=c[x]; return as; }void upt(int x, ll v){ add(in[x],v); add(out[x]+1, -v); }
}
ll work(int x){if(!x) return 0;ll f = work(ch[x][0]) + work(ch[x][1]), g = INF, sm = 0;for(auto c : G[x])g = min(g, f - c.se + dlt::qry(in[ps[c.fi]])), sm += c.se;f += sm; g += sm; dlt::upt(x, f-min(f,g)); return min(f,g);
}
int main(){n=read();for(int i=2; i<=n; i++) lg[i]=lg[i>>1]+1;for(int i=1; i<=n; i++) a[i]=read();for(int i=1; i<=n; i++) mn[0][i]=i;for(int i=1; (1<<i)<=n; i++)for(int j=1; j+(1<<i)-1<=n; j++)mn[i][j]=chk(mn[i-1][j],mn[i-1][j+(1<<(i-1))]); build(1,n);m=read();for(int i=1; i<=m; i++){o[i].x=read(), o[i].y=read(), o[i].c=read();} sort(o+1, o+m+1, [](cs star &a, cs star &b){ return a.x < b.x; });static int l[N], r[N];for(int i=1, j=1; i<=n; i++){while(o[j].x==i) l[j]=SGT::qry(1,1,n,o[j].y), ++j;SGT::modify(1,1,n,a[i],i);}memset(SGT::tag,0,sizeof(SGT::tag));for(int i=n, j=m; i>=1; i--){while(o[j].x==i) r[j]=n-SGT::qry(1,1,n,o[j].y)+1, --j;SGT::modify(1,1,n,a[i],n-i+1);} for(int i=1; i<=m; i++) G[mp[pi(l[i]+1,r[i]-1)]].pb(pi(o[i].x,o[i].c));dfs(1); cout << work(1); return 0; 
}