当农夫约翰闲的没事干的时候，他喜欢坐下来看书。多年过去，他已经收集了 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
     
      #include
      
       #include
       
        #define N 100002using namespace std;typedef long long ll;long long tr[N<<2],sum[N],w[N],m,n,h[N],x,q[N],la[N<<2],ans[N<<2];inline void pushdown(int cnt){    la[cnt<<1]=la[cnt<<1|1]=la[cnt];la[cnt]=0;     ans[cnt<<1]=tr[cnt<<1]+la[cnt<<1];ans[cnt<<1|1]=tr[cnt<<1|1]+la[cnt<<1|1];}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)>>1;    if(la[cnt])pushdown(cnt);    if(mid>=x)add(cnt<<1,l,mid,x,y);    else add(cnt<<1|1,mid+1,r,x,y);    tr[cnt]=min(tr[cnt<<1],tr[cnt<<1|1]);    ans[cnt]=min(ans[cnt<<1],ans[cnt<<1|1]);}ll query(int cnt,int l,int r,int L,int R){     if(l>=L&&r<=R)return ans[cnt];    int mid=(l+r)>>1;    ll ans=1e18;    if(la[cnt])pushdown(cnt);    if(mid>=L)ans=min(ans,query(cnt<<1,l,mid,L,R));    if(mid
        
         <<1|1,mid+1,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)>>1;    if(la[cnt])pushdown(cnt);    if(mid>=L)upd(cnt<<1,l,mid,L,R,x);    if(mid
         
          <<1|1,mid+1,r,L,R,x);    tr[cnt]=min(tr[cnt<<1],tr[cnt<<1|1]);    ans[cnt]=min(ans[cnt<<1],ans[cnt<<1|1]);}int find(int x){    int l=0,r=x,ans;    while(l<=r){        int mid=(l+r)>>1;        if(sum[x]-sum[mid]<=m){            ans=mid;            r=mid-1;        }         else l=mid+1;    }    return ans;} int main(){    scanf("%lld%lld",&n,&m);    memset(tr,0x3f,sizeof(tr));memset(ans,0x3f,sizeof(ans));    for(int i=1;i<=n;++i)scanf("%lld%lld",&h[i],&w[i]),sum[i]=sum[i-1]+w[i];    int mn=0;    add(1,0,n,0,0);    int hh,t;    hh=t=1;q[hh]=0;    for(int i=1;i<=n;++i){        while(hh<=t&&h[q[t]]