USACO12OPEN-Bookshelf G

[USACO12OPEN]Bookshelf G

题意

考虑现在有 $n$ 本书并给定一个最大长度 $L$，第 $i$ 本书有高度 $h_i,w_i$。每次选取一段范围满足该段范围内的所有书的 $\sum w_i\leq L$，那么这次选取的贡献为 $\max\{h_i\}$。

Sol

考虑暴力 dp 转移方程

$dp_i = \min\{dp_j + \max\{ h_k \}_{ j < k < i }\}_{ 1 \leq j < i , \sum_{k=j}^{i}w_k \leq L }$

对于 $\sum w_i\leq L$ 的限制我们可以视为类似滑动窗口，依据上式很容易想到单调队列。

但是我们发现构造的单调队列里的每个数都由 $dp,\max\{h\}$ 两个值组成，并且 $\max\{h\}$ 会随队尾所加入的数影响，单纯的单调队列我们无法处理这类问题，此时考虑使用数据结构加以维护。

或者说，本题依据暴力 dp 转移方程本就可以考虑使用数据结构维护，那么此时我们考虑使用线段树。

依据观察得出几条有助于我们维护线段树的性质：

1. 线段树中叶子结点从 $1$ 到 $n$ 依次加入，每次加入的 $h_i$ 会对 $[1,i]$ 中的数产生影响。
2. 当前对区间修改的参数 $k$ 如果满足 $\forall h_i\geq k$，该区间将不会产生任何影响。
3. 由于我们的叶子结点依次加入，我们总是考虑将 $\min\{dp_i\}$ 作为答案的一部分。
4. 同理，我们仍可以将 $\max\{h_i\}$ 作为答案的一部分。
5. 所以一个区间的贡献为 $\min\{dp_i\}+\max\{h_i\}$，而两个区间的贡献合并时取 $\min$。
6. 依据以上，当前对区间修改的参数 $k$ 如果满足 $\forall h_i < k$，我们可以直接，对区间信息进行修改。

那么我们考虑对于每个结点维护 $h,f,t,w$ 分别表示 $\max\{h_i\},\min\{dp_i\},\min\{h_i\},\min\{h_i + dp_i\}$。

并对于区间修改操作时依据上述的第 2 点和第 6 点分类进行，注意答案会爆 long long，查询时的 inf 值也一并开到 $5\times 10^{10}$ 以上。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,MAXN=2e5+1e1,Tp=1e9;
const lint INF=1e15+1e9;

struct Node{// h max, w, t, min
	int l,r;
	lint h,t,f,w,lazy;
};

lint h[MAXN],s[MAXN],f[MAXN],l[MAXN],m;
int n,Head;

struct SegmentTree{
	Node tree[MAXN<<2];

	void Pushup(int x){
		int l=tree[x].l,r=tree[x].r;
		if(l!=r) tree[x].h=max(tree[x<<1].h,tree[x<<1|1].h),
				tree[x].t=min(tree[x<<1].t,tree[x<<1|1].t),
				tree[x].w=min(tree[x<<1].w,tree[x<<1|1].w),
				tree[x].f=min(tree[x<<1].f,tree[x<<1|1].f);
		return;
	}

	void Build(int l,int r,int x){
		tree[x].l=l,tree[x].r=r;
		if(l!=r){
			int mid=l+r>>1;
			Build(l,mid,x<<1),Build(mid+1,r,x<<1|1);
		}
		return;
	}

	void Pushdown(int x){
		if(tree[x].lazy){
			tree[x<<1].t=tree[x<<1|1].t=tree[x].lazy;
			tree[x<<1].h=tree[x<<1|1].h=tree[x].lazy;
			tree[x<<1].lazy=tree[x<<1|1].lazy=tree[x].lazy;
			tree[x<<1].w=tree[x<<1].h+tree[x<<1].f;
			tree[x<<1|1].w=tree[x<<1|1].h+tree[x<<1|1].f;
		}
		tree[x].lazy=0;
		return;
	}

	void Insert(int p,int x){
		int l=tree[x].l,r=tree[x].r;
		if(p<l || r<p) return;
		if(l==p && p==r){
			tree[x].f=f[p],tree[x].h=tree[x].t=h[p];
			tree[x].w=tree[x].h+tree[x].f;
		}
		else Pushdown(x),Insert(p,x<<1),Insert(p,x<<1|1),Pushup(x);
		return;
	}

	void Update(int ql,int qr,lint k,int x){
		int l=tree[x].l,r=tree[x].r;
		if(qr<l || r<ql) return;
		if(ql<=l && r<=qr){
			if(tree[x].h<k){
				tree[x].t=tree[x].h=tree[x].lazy=k;
				tree[x].w=tree[x].f+k;
			}
			else{
				Pushdown(x);
				if(tree[x<<1].t<k) Update(ql,qr,k,x<<1);
				if(tree[x<<1|1].t<k) Update(ql,qr,k,x<<1|1);
				Pushup(x);
			}
		}
		else Pushdown(x),Update(ql,qr,k,x<<1),Update(ql,qr,k,x<<1|1),Pushup(x);
		return;
	}

	lint Query(int ql,int qr,int x){
		int l=tree[x].l,r=tree[x].r;
		if(qr<l || r<ql) return INF;
		lint res=INF;
		if(ql<=l && r<=qr) res=tree[x].w;
		else{
			Pushdown(x);
			res=min(Query(ql,qr,x<<1),res);
			res=min(Query(ql,qr,x<<1|1),res);
		}
		return res;
	}
}st;

int main(void){

	scanf("%d%lld",&n,&m),st.Build(1,n,1);
	for(int i=1;i<=n;i++) h[i]=readlint,l[i]=readlint;
	for(int i=1;i<=n;i++) s[i]=s[i-1]+l[i];
	for(int i=1;i<=n;i++){
		while(Head<i && s[Head]+m<s[i]) ++Head;
		st.Update(1,i,h[i],1);
		f[i+1]=st.Query(Head+1,i,1);
		st.Insert(i+1,1);
	}
	printf("%lld\n",f[n+1]);

	return 0;
}