Description

当农夫约翰闲的没事干的时候，他喜欢坐下来看书。多年过去，他已经收集了 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没法维护啊，最后弄出一个暴力均摊的线段树做法.

\(f[i]=f[j]+v[j+1][i]\)，这是原DP方程，\(v[j][i]\)表示\(j-i\)间的最大值.

考虑优化：

我们在线段树中，分别维护 \(f[j]\) 和 \(v[j]\)，单调指针扫描，扫到 \(i\) 时，用 \(H[i]\) 取更新 \([1,i-1]\) 的 \(v\) 值.

再维护一个\(f[j]+v[j]\)，那么转移就是线段树查最值了.

关键在于修改的复杂度：

维护一个区间最小值和区间最大值：

1.如果最小值大于 \(H[i]\)，那么没有修改的必要，直接返回

2.如果最大值小于 \(H[i]\)，那么直接打上覆盖标记即可

复杂度的证明：

一个无单调性的序列经过一次暴力修改之后，就会变成单调递增或递减序列了，那么下一次修改就会只会选择其中一部分进行修改(因为另一部分总会碰到上述两个剪枝中的一种情况)，并且修改完之后依旧是满足单调性的，所以除了第一次修改之外，之后就是线段树修改的复杂度了，均摊 \(O(n*logn)\)，常数有些大

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define RG register#define ls (o<<1)#define rs (o<<1|1)#define Min(a,b) ((a)<(b)?(a):(b))#define Max(a,b) ((a)>(b)?(a):(b))using namespace std;typedef long long ll;const int N=100005;const ll inf=1e15;int n,m,v[N],lazy[N<<2],mx[N<<2],mn[N<<2];ll f[N<<2],a[N],g[N<<2];inline void upd(RG int o){ f[o]=Min(f[ls],f[rs]); mx[o]=Max(mx[ls],mx[rs]); mn[o]=Min(mn[ls],mn[rs]);}inline void pushdown(RG int o){ if(!lazy[o])return ; int k=lazy[o]; f[ls]=g[ls]+k;mx[ls]=k;mn[ls]=k; f[rs]=g[rs]+k;mx[rs]=k;mn[rs]=k; lazy[ls]=k;lazy[rs]=k; lazy[o]=0;}inline void Modify(int l,int r,int o,int sa,int se,int t){ if(l!=r)pushdown(o); if(mn[o]>=t)return ; if(sa<=l && r<=se){ if(mx[o]
          
           >1; if(se<=mid)Modify(l,mid,ls,sa,se,t); else if(sa>mid)Modify(mid+1,r,rs,sa,se,t); else Modify(l,mid,ls,sa,mid,t),Modify(mid+1,r,rs,mid+1,se,t); upd(o);}inline void updata(int l,int r,int o,int sa,ll t){ if(l==r){g[o]=t;return ;} int mid=(l+r)>>1; pushdown(o); if(sa<=mid)updata(l,mid,ls,sa,t); else updata(mid+1,r,rs,sa,t); g[o]=Min(g[ls],g[rs]);}inline ll qry(int l,int r,int o,int sa,int se){ if(l!=r)pushdown(o); if(sa<=l && r<=se)return f[o]; int mid=(l+r)>>1;ll ret,q1,q2; if(se<=mid)ret=qry(l,mid,ls,sa,se); else if(sa>mid)ret=qry(mid+1,r,rs,sa,se); else{ q1=qry(l,mid,ls,sa,mid),q2=qry(mid+1,r,rs,mid+1,se); ret=Min(q1,q2); } upd(o); return ret;}int l=0;void work(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d%lld",&v[i],&a[i]),a[i]+=a[i-1]; ll tmp; for(int i=1;i<=n;i++){ while(l
           m)l++; Modify(0,n,1,0,i-1,v[i]); tmp=qry(0,n,1,l,i-1); if(i!=n)updata(0,n,1,i,tmp); } cout<
            
             <