【传送门：51nod-1611】
简要题意：
给出n个点，编号为1到n，一开始每个点都是不可用状态，要花费c[i]的代价才能使第i个点变为可用点
有m个奖励区间，每个区间输入l,r,d，表示如果l到r的点都为可用状态则获得d的价值
求出最大能获得的价值
题解：
先DP一手，设f[i]为到第i个点能得到的最大价值（第i个点可选可不选）
显然转移为有两种情况
1.不选第i个点则$f[i]=f[i-1]$
2.选第j+1个点到第i个点则$f[i]=f[j]-sum_{k=j+1}^{i}c[k]+D$
显然代价我们可以前缀和得到，设$s[i]=sum_{j=1}^{i}c[i]$而我们只需要处理j+1到i的区间中包含的奖励区间就可以了
那么显然我们可以用线段树来维护，对于线段树中第j个点，我们维护第j个点为f[j]+s[j]+D，这个D为当前枚举到第i个点时所有右端点在i或i的左边，左端点在j的右边的奖励区间的价值和，显然我们可以将奖励区间按照当前的i点来依次插入线段树，若当前奖励区间为l到r，价值为d，则将线段树中1到l-1的位置上的数都加上d，那么我们每次转移只需要在线段树中找到一个最大值，然后将f[i]=这个值-s[i]就可以了，因为等价于f[i]=f[j]+s[j]-s[i]+D
然后细节还是看代码吧
参考代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; inline int read() { LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10LL+ch-'0';ch=getchar();} return x*f; } struct trnode { int l,r,lc,rc; LL c,lazy; }tr[410000];int trlen; LL c[210000]; inline void bt(int l,int r) { trlen++;int now=trlen; tr[now].l=l;tr[now].r=r;tr[now].c=tr[now].lazy=0; tr[now].lc=tr[now].rc=-1; if(l==r) tr[now].c=c[l]; else { int mid=(l+r)/2; tr[now].lc=trlen+1;bt(l,mid); tr[now].rc=trlen+1;bt(mid+1,r); tr[now].c=max(tr[tr[now].lc].c,tr[tr[now].rc].c); } } inline void update(int now) { int lc=tr[now].lc,rc=tr[now].rc; if(lc!=-1) { tr[lc].c+=tr[now].lazy; tr[lc].lazy+=tr[now].lazy; } if(rc!=-1) { tr[rc].c+=tr[now].lazy; tr[rc].lazy+=tr[now].lazy; } tr[now].lazy=0; } inline void change(int now,int l,int r,LL d) { if(tr[now].l==l&&tr[now].r==r) { tr[now].c+=d; tr[now].lazy+=d; return ; } int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2; if(tr[now].lazy!=0) update(now); if(r<=mid) change(lc,l,r,d); else if(l>mid) change(rc,l,r,d); else change(lc,l,mid,d),change(rc,mid+1,r,d); tr[now].c=max(tr[lc].c,tr[rc].c); } inline LL findmax(int now,int l,int r) { if(tr[now].l==l&&tr[now].r==r) return tr[now].c; int lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2; if(tr[now].lazy!=0) update(now); if(r<=mid) return findmax(lc,l,r); else if(l>mid) return findmax(rc,l,r); else return max(findmax(lc,l,mid),findmax(rc,mid+1,r)); } struct node { int l,r;LL d; }R[210000]; bool cmp(node n1,node n2){return n1.r==n2.r?n1.l<n2.l:n1.r<n2.r;} LL f[210000]; int main() { int n=read(),m=read(); for(int i=1;i<=n;i++) c[i]=read(),c[i]+=c[i-1]; for(int i=1;i<=m;i++) R[i].l=read(),R[i].r=read(),R[i].d=read(); sort(R+1,R+m+1,cmp); trlen=0;bt(1,n); int x=0; f[0]=0; for(int i=1;i<=n;i++) { f[i]=f[i-1]; while(x+1<=m&&R[x+1].r<=i) { x++; if(R[x].l>1) change(1,1,R[x].l-1,R[x].d); f[0]+=R[x].d; } if(i>1) f[i]=max(f[i],max(f[0]-c[i],findmax(1,1,i-1)-c[i])); else f[i]=max(f[i],f[0]-c[i]); change(1,i,i,f[i]); } printf("%lld ",f[n]); return 0; }