[TJOI2011] 书架

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
using namespace std;
struct dat
{int val,wei,ff;};
dat line[100005];
int tre[500005],book[100005],qian[100005],f[100005],n,m,h,t,head,tail,s,p,ma;
void jia(int wei,int val,int l,int r,int root)
{
    if (l==r){tre[root]=val;return;}
    int mid=(l+r)/2;
    if (wei<=mid)jia(wei,val,l,mid,root*2);
    else jia(wei,val,mid+1,r,root*2+1);
    tre[root]=min(tre[root*2],tre[root*2+1]);
}
int fid(int h,int t,int l,int r,int root)
{
    if (l==r){return tre[root];}
    if (h<=l && t>=r)return tre[root];
    int mid=(l+r)/2,mm=1000000007;
    if (h<=mid)mm=fid(h,t,l,mid,root*2);
    if (t>=mid+1) mm=min(mm,fid(h,t,mid+1,r,root*2+1));
    return mm;
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&book[i]);
    }
    h=1;head=1;tail=0;
    while (t<n && s+book[t+1]<=m)
    {
         t++;s+=book[t];qian[t]=1;ma=max(ma,book[t]);f[t]=ma;
         while (tail>0 && book[t]>=line[tail].val)tail--;
         tail++;line[tail].val=book[t];line[tail].wei=t;line[tail].ff=line[tail-1].wei;
         jia(tail,f[line[tail-1].wei]+book[t],1,n,1);
    }
    for (int i=t+1;i<=n;i++)
    {
        s+=book[i];
        while (s>m){s-=book[h];h++;}
        qian[i]=h;
    }
     for (int i=t+1;i<=n;i++)
     {
         while (line[head].wei<qian[i] && head<=tail){line[head].wei=0;head++;}
         if (line[head].ff<qian[i]-1){line[head].ff=qian[i]-1;jia(head,f[qian[i]-1]+line[head].val,1,n,1);}
         while (tail>=head && book[i]>=line[tail].val){tail--;}
         tail++;line[tail].val=book[i];line[tail].wei=i;line[tail].ff=max(line[tail-1].wei,qian[i]-1);
         jia(tail,f[line[tail].ff]+book[i],1,n,1);
         f[i]=fid(head,tail,1,n,1);
     }
     cout<<f[n];
}