线段树优化DP

AC记录：

运行时间完爆zmrzmr的单调队列优化+双指针 p[i]表示右端点小于i的左端点的最大值,f[i]表示将左端点在i这个位置前的所有线段覆盖的最小花费 $$f[i]=min {f[j]}~(p[i]<=j<i)~$$ 用线段树查询最小值 时间复杂度 $$ O(nlogn) $$

注意

要将n加一，花费计算到n+1，否则下面这样的数据将无法通过（我在这个地方卡了一小时）

5
1 1 1 1 1
2
1 5
4 5

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int N=5e5+10;
int n,a[N],m,f[N],mx[N];
struct tree {
	int l,r,minn;
} tr[N*4];
struct node {
	int l,r;
	bool operator<(const node &x) {
		return r<x.r;
	}
} line[N];
void build(int u,int l,int r) {
	tr[u]= {l,r};
	if(l==r) return;
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}
void pushup(int u) {
	tr[u].minn=min(tr[u<<1].minn,tr[u<<1|1].minn);

}
int query(int u,int l,int r) {
	if(l<=tr[u].l&&tr[u].r<=r) return tr[u].minn;
	int ans=0;
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) ans=query(u<<1,l,r);
	if(r>mid) ans=(ans==0?query(u<<1|1,l,r):min(ans,query(u<<1|1,l,r)));
	return ans;
}
void modify(int u,int x,int v) {
	if(tr[u].l==x&&tr[u].r==x)     tr[u].minn=v;
	else {
		int mid=tr[u].l+tr[u].r>>1;
		if(x<=mid) modify(u<<1,x,v);
		else modify(u<<1|1,x,v);
		pushup(u);
	}
}
int query2(int pos) {
	int i=lower_bound(line+1,line+1+m,node{0,pos})-line-1;
	return mx[i];
}
signed main() {
	cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	cin>>m;
	for(int i=1; i<=m; i++) cin>>line[i].l>>line[i].r;
	sort(line+1,line+1+m);
	mx[0]=0;
	for(int i=1; i<=m; i++) mx[i]=max(line[i].l,mx[i-1]);
	build(1,1,n+1);
	for(int i=1; i<=n+1; i++) {
		int lastpos=query2(i);
		if(lastpos==0) f[i]=a[i];
		else f[i]=query(1,lastpos,i-1)+a[i];
		modify(1,i,f[i]);
	}
	int ans=2e9;
	//for(int i=max(1LL,query2(n));i<=n;i++) ans=min(ans,f[i]);
	cout<<f[n+1];
}