这是本蒟蒻写的第一篇题解（写不好请指出）
很明显他是一道dp题，因为第i本书放哪里只跟前i-1本树的放法有关系。
我们可以是定义f[i][j]表示放了i本书，最后一层书架是以第j本书开始的。
那么有动态转移方程：
\(f[i][i]=min(f[i-1][j])+hi,w[j]+...+w[i-1]<=L\)
\(f[i][j]=f[i-1][j]+max(0,h[i]-max(h[j],..h[i-1]))\)
\(w[j]+w[j+1]+...+w[i]<=L\)
下面思考优化：
1、可以使用单调栈，求出最小的满足条件的j
2、使用平衡树寻找h[j]~h[i-1]中最后一个大于等于h[i]的数的wz，然后修改wz以后的数
3、构造线段树来优化更新时间O(log n)。线段树要记录：
last->倒数第二层书架到第一层书架的高度
now->倒数第一层书架的高度
ans->总高度
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=100500,INF=1e17;
ll n,L;
ll hi[N],wi[N];
struct jgt
{
ll l,r;
ll key,val;
ll xb,zdxb;
ll head;
}tr[N];
ll root,idx;
ll get_node(ll x,ll wz)
{
tr[++idx].xb=wz;
tr[idx].zdxb=wz;
tr[idx].key=x;
tr[idx].val=rand();
tr[idx].head=wz;
return idx;
}
void pushup(ll p)
{
tr[p].zdxb=max(tr[p].xb,max(tr[tr[p].l].zdxb,tr[tr[p].r].zdxb));
return ;
}
void yx(ll &p)
{
ll q=tr[p].l;
tr[p].l=tr[q].r;
tr[q].r=p;
pushup(p);
p=q;
pushup(p);
return ;
}
void zx(ll &p)
{
ll q=tr[p].r;
tr[p].r=tr[q].l;
tr[q].l=p;
pushup(p);
p=q;
pushup(p);
return ;
}
void add(ll &p,ll x,ll wz)
{
if(!p)
{
p=get_node(x,wz);
return ;
}
if(x<tr[p].key)
{
add(tr[p].l,x,wz);
if(tr[tr[p].l].val>tr[p].val) yx(p);
pushup(p);
return ;
}
if(x==tr[p].key)
{
tr[p].xb=max(tr[p].xb,wz);
pushup(p);
return ;
}
if(x>tr[p].key)
{
add(tr[p].r,x,wz);
if(tr[tr[p].r].val>tr[p].val) zx(p);
pushup(p);
return ;
}
return ;
}
void remove(ll &p,ll x,ll wz)
{
if(!p) return ;
if(x<tr[p].key)
{
remove(tr[p].l,x,wz);
pushup(p);
return ;
}
if(x>tr[p].key)
{
remove(tr[p].r,x,wz);
pushup(p);
return ;
}
if(x==tr[p].key)
{
if(wz!=tr[p].xb) return ;
if(!tr[p].l&&!tr[p].r)
{
p=0;
pushup(p);
return ;
}
if(!tr[p].r&&tr[tr[p].l].val>tr[tr[p].r].val)
{
yx(p);
remove(tr[p].r,x,wz);
pushup(p);
return ;
}
else
{
zx(p);
remove(tr[p].l,x,wz);
pushup(p);
}
}
}
ll query(ll p,ll x)
{
if(!p) return -INF;
if(x>=tr[p].key) return query(tr[p].r,x);
return max(query(tr[p].l,x),max(tr[tr[p].r].zdxb,tr[p].xb));
}
//平衡树
struct jgt1
{
ll last,now;
ll ans;
}xdtr[N*8];
void gai(ll wz,ll l,ll r,ll md,ll la,ll no)
{
if(l==md&&r==md)
{
xdtr[wz].last=la;
xdtr[wz].now=no;
xdtr[wz].ans=la+no;
return ;
}
ll mid=(l+r)/2;
if(md<=mid) gai(wz*2,l,mid,md,la,no);
else gai(wz*2+1,mid+1,r,md,la,no);
if(xdtr[wz*2].last<xdtr[wz*2+1].last)
{
xdtr[wz].last=xdtr[wz*2].last;
xdtr[wz].now=xdtr[wz*2].now;
}
else if(xdtr[wz*2].last==xdtr[wz*2+1].last)
{
xdtr[wz].last=xdtr[wz*2].last;
xdtr[wz].now=min(xdtr[wz*2].now,xdtr[wz*2+1].now);
}
else
{
xdtr[wz].last=xdtr[wz*2+1].last;
xdtr[wz].now=xdtr[wz*2+1].now;
}
xdtr[wz].ans=min(xdtr[wz*2].ans,xdtr[wz*2+1].ans);
}
ll tag[N*8];
void pushdown(ll wz,ll l,ll r)
{
tag[wz*2]=tag[wz];
tag[wz*2+1]=tag[wz];
xdtr[wz*2].now=tag[wz];
xdtr[wz*2+1].now=tag[wz];
xdtr[wz*2].ans=xdtr[wz*2].now+xdtr[wz*2].last;
xdtr[wz*2+1].ans=xdtr[wz*2+1].now+xdtr[wz*2+1].last;
tag[wz]=-1;
return ;
}
void xg(ll wz,ll l,ll r,ll le,ll ri,ll no)
{
if(tag[wz]!=-1) pushdown(wz,l,r);
if(le<=l&&ri>=r)
{
xdtr[wz].now=no;
xdtr[wz].ans=xdtr[wz].now+xdtr[wz].last;
tag[wz]=no;
return ;
}
ll mid=(l+r)/2;
if(le<=mid) xg(wz*2,l,mid,le,ri,no);
if(ri>mid) xg(wz*2+1,mid+1,r,le,ri,no);
if(xdtr[wz*2].last<xdtr[wz*2+1].last)
{
xdtr[wz].last=xdtr[wz*2].last;
xdtr[wz].now=xdtr[wz*2].now;
}
else if(xdtr[wz*2].last==xdtr[wz*2+1].last)
{
xdtr[wz].last=xdtr[wz*2].last;
xdtr[wz].now=min(xdtr[wz*2].now,xdtr[wz*2+1].now);
}
else
{
xdtr[wz].last=xdtr[wz*2+1].last;
xdtr[wz].now=xdtr[wz*2+1].now;
}
xdtr[wz].ans=min(xdtr[wz*2].ans,xdtr[wz*2+1].ans);
}
ll find(ll wz,ll l,ll r,ll le,ll ri)
{
if(tag[wz]!=-1) pushdown(wz,l,r);
if(le<=l&&ri>=r) return xdtr[wz].ans;
ll mid=(l+r)/2,ans=INF;
if(le<=mid) ans=min(ans,find(wz*2,l,mid,le,ri));
if(ri>mid) ans=min(ans,find(wz*2+1,mid+1,r,le,ri));
return ans;
}
//线段树
ll zz=1,zh;
//指针
void init()
{
tr[0].xb=-INF;
tr[0].zdxb=-INF;
}
//初始化
ll tzy;
//一些无用的tzy
int main()
{
memset(tag,-1,sizeof tag);
init();
scanf("%lld %lld",&n,&L);
for(ll i=1;i<=n;i++)
scanf("%lld %lld",&hi[i],&wi[i]);
zz=1;
zh=wi[1];
add(root,hi[1],1);
gai(1,1,n,1,0,hi[1]);
for(ll i=2;i<=n;i++)
{
tzy=find(1,1,n,zz,i-1);
gai(1,1,n,i,tzy,hi[i]);
zh+=wi[i];
while(zh>L)
{
zh-=wi[zz];
remove(root,hi[zz],zz);
zz++;
}
tzy=query(root,hi[i]);
add(root,hi[i],i);
if(tzy==-INF) tzy=zz-1;
tzy++;
if(tzy<=i-1) xg(1,1,n,tzy,i-1,hi[i]);
}
printf("%lld\n",find(1,1,n,zz,n));
return 0;
}