【题解 && 优化dp】 B - Base Station Construction

题目描述：

分析：

当dp状态设定不好的时候，我们不妨从最简单的部分出发
设$f_i$表示必须在第i个点建设基站，并且i号点之前的线段全部满足要求时所需要的最小代价

为什么这么设呢？
这道题想要入手，无非就两个点
一个是点，一个是线段。

我刚开始其实想从线段入手，但是发现重叠的部分根本不好处理，以至于我被卡了思路，一直到结束

因此适当时我们需要转换思路，从点出发进行考虑。

以点为状态设dp方程是有好处的，那就是转移十分简单：
$$f_i=mi{n}_j(f_j)+a_i$$
j表示我们上一个建基站的位置（注意，是上一个！也就是说在$[j+1,i?1]$这段区间里面我们没有其他基站设立）

这样表示显然是没问题的，因为除了第一个基站，其他基站的设立必定是存在上一个基站的。

但是这个j显然不能乱找，怎么样去找这个j才是合法的呢？
我们注意到题目要求：每一条线段上都必须要有一个基站存在。
所以，这个j是合法的当且仅当$[j+1,i?1]$之间不存在一条完整的的线段。

这个j的位置显然是需要经过预处理的。
我们$Ma{x}_i$用记录最小的一个位置$p$，满足在$[p,i]$之间不存在任何完整的线段。

随着位置i的增加，位置$Ma{x}_i$显然是递增的。
所以我们维护一个前缀最大值即可。

所以j的合法位置就是$[Ma{x}_{j?1}?1,i?1]$
求一个区间最小值即可
线段树或者单调队列都可
这边用的是线段树

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+100;
int n,m;
int a[N],f[N];
int maxl[N];
int Max[N];

struct Tr{
	int tr[4*N];
	void Build(int x,int l,int r){
		if (l == r){
			tr[x] = 5e14+1;
			return;
		}
		int Mid = l+r>>1;
		Build(x<<1,l,Mid); Build(x<<1|1,Mid+1,r);
		tr[x] = min(tr[x<<1],tr[x<<1|1]);
	}
	void Insert(int x,int l,int r,int k,int v){
		if (l == r){
			tr[x] = min(tr[x],v);
			return;
		}
		int Mid = l+r>>1;
		if (k <= Mid) Insert(x<<1,l,Mid,k,v);
		else Insert(x<<1|1,Mid+1,r,k,v);
		tr[x] = min(tr[x<<1],tr[x<<1|1]);
		return;
	}
	int Ask(int x,int l,int r,int L,int R){
		if (L <= l && r <= R) return tr[x];
		int Mid = l+r>>1,Min = 5e15+1;
		if (L <= Mid) Min = min(Min,Ask(x<<1,l,Mid,L,R));
		if (R > Mid) Min = min(Min,Ask(x<<1|1,Mid+1,r,L,R));
		return Min;
	}
}tr;

void Work(){
	scanf("%d",&n);
	for (int i = 1; i <= n; i++) scanf("%d",&a[i]); ++n;
	scanf("%d",&m);
	for (int i = 1,l,r; i <= m; i++){
		scanf("%d %d",&l,&r);
		maxl[r] = max(maxl[r],l);
	}
	int l = 1;
	f[1] = a[1]; f[0] = 0;
	tr.Build(1,0,n);
	tr.Insert(1,0,n,1,a[1]);
	tr.Insert(1,0,n,0,0);
	for (int i = 1; i <= n; i++){
		Max[i] = max(Max[i-1],maxl[i]+1);
	}
	for (int i = 2; i <= n; i++){
		f[i] = tr.Ask(1,0,n,Max[i-1]-1,i-1)+a[i];
		tr.Insert(1,0,n,i,f[i]);
	}
	cout<<f[n]<<endl;
	for (int i = 1; i <= n; i++) a[i] = 0,maxl[i] = 0;
	return;
}

signed main(){
	int t;
	cin>>t;
	while (t--) Work(); 
	return 0;
}