当农夫约翰闲的没事干的时候，他喜欢坐下来看书。多年过去，他已经收集了 N 本书 (1 <= N <= 100,000)， 他想造一个新的书架来装所有书。
每本书 i 都有宽度 W(i) 和高度 H(i)。书需要按顺序添加到一组书架上；比如说，第一层架子应该包含书籍1 ... k，第二层架子应该以第k + 1本书开始，以下如此。每层架子的总宽度最大为L（1≤L≤1,000,000,000）。每层的高度等于该层上最高的书的高度，并且整个书架的高度是所有层的高度的总和，因为它们都垂直堆叠。
请帮助农夫约翰计算整个书架的最小可能高度。
有N(1 <= N <= 100000)本书，每本书有一个宽度W(i)，高度H(i)，(1 <= H(i) <= 1,000,000; 1 <= W(i) <= L)。
现在有足够多的书架，书架宽度最多是L (1 <= L <= 1,000,000,000)，把书按顺序（先放1，再放2.....）放入书架。某个书架的高度是该书架中所放的最高的书的高度。
将所有书放入书架后，求所有书架的高度和的最小值？
Solution
一眼dp优化。
状态方程显然，dp[[i]=dp[j]+maxh(j~i).然后用线段树优化，区间取max，单点修改。
但答案是两部分构成的，区间取max会炸。。
于是我想了一晚上。。。
我们发现每次取max会改变一段连续的区间，所以我们维护一个单调递减的队列，每次找到前面第一个比它大的点，直接区间修改就可以了。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100002
using namespace std;
typedef long long ll;
long long tr[N<<],sum[N],w[N],m,n,h[N],x,q[N],la[N<<],ans[N<<];
inline void pushdown(int cnt){
la[cnt<<]=la[cnt<<|]=la[cnt];la[cnt]=;
ans[cnt<<]=tr[cnt<<]+la[cnt<<];ans[cnt<<|]=tr[cnt<<|]+la[cnt<<|];
}
void add(int cnt,int l,int r,int x,ll y){
if(l==r){
tr[cnt]=y;
ans[cnt]=y+la[cnt];
return;
}
int mid=(l+r)>>;
if(la[cnt])pushdown(cnt);
if(mid>=x)add(cnt<<,l,mid,x,y);
else add(cnt<<|,mid+,r,x,y);
tr[cnt]=min(tr[cnt<<],tr[cnt<<|]);
ans[cnt]=min(ans[cnt<<],ans[cnt<<|]);
}
ll query(int cnt,int l,int r,int L,int R){
if(l>=L&&r<=R)return ans[cnt];
int mid=(l+r)>>;
ll ans=1e18;
if(la[cnt])pushdown(cnt);
if(mid>=L)ans=min(ans,query(cnt<<,l,mid,L,R));
if(mid<R)ans=min(ans,query(cnt<<|,mid+,r,L,R));
return ans;
}
void upd(int cnt,int l,int r,int L,int R,ll x){
if(L>R)return;
if(l>=L&&r<=R){
la[cnt]=x;
ans[cnt]=tr[cnt]+la[cnt];
return;
}
int mid=(l+r)>>;
if(la[cnt])pushdown(cnt);
if(mid>=L)upd(cnt<<,l,mid,L,R,x);
if(mid<R)upd(cnt<<|,mid+,r,L,R,x);
tr[cnt]=min(tr[cnt<<],tr[cnt<<|]);
ans[cnt]=min(ans[cnt<<],ans[cnt<<|]);
}
int find(int x){
int l=,r=x,ans;
while(l<=r){
int mid=(l+r)>>;
if(sum[x]-sum[mid]<=m){
ans=mid;
r=mid-;
}
else l=mid+;
}
return ans;
}
int main(){
scanf("%lld%lld",&n,&m);
memset(tr,0x3f,sizeof(tr));memset(ans,0x3f,sizeof(ans));
for(int i=;i<=n;++i)scanf("%lld%lld",&h[i],&w[i]),sum[i]=sum[i-]+w[i];
int mn=;
add(,,n,,);
int hh,t;
hh=t=;q[hh]=;
for(int i=;i<=n;++i){
while(hh<=t&&h[q[t]]<h[i])t--;
upd(,,n,hh<=t?q[t]:,i-,h[i]);
q[++t]=i;
x=query(,,n,find(i),i-);
add(,,n,i,x);
}
printf("%lld",x);
return ;
}