线段树优化 dp 写法

WA 了一半/kk

// wish to get better qwq

#include<bits/stdc++.h>
#define re register int
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define dec(x) fixed<<setprecision(x)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

template<class T> inline void rd(T &x){
	int fl=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	x*=fl;
}
template<class T> inline void wr(T x){
	if(x<0) x=-x,putchar('-');
	if(x<10){putchar(x+'0');return ;}
	int tmp[30]={0},cnt=0;
	while(x) tmp[cnt++]=x%10,x/=10;
	for(re i=cnt-1;i>=0;--i) putchar(tmp[i]+'0');
}

// ---------- IO ---------- //

const int N=1e5+5;const ll INF=1e18;
int n,pre[N],tp;
ll len,w[N],h[N],s[N],f[N],st[N];

struct SGT{
	#define mid ((l+r)>>1)
	#define xl (x<<1)
	#define xr (x<<1|1)
	ll minf[N],fh[N],tag[N];
	inline void pushup(int x){
		minf[x]=min(minf[xl],minf[xr]);
		fh[x]=min(fh[xl],fh[xr]);
	}
	inline void build(int x,int l,int r){
		if(l==r){
			minf[x]=fh[x]=tag[x]=INF;
			return ;
		}
		build(xl,l,mid);build(xr,mid+1,r);
		pushup(x);
	}
	inline void pushdown(int x){
		if(tag[x]!=INF){
			tag[xl]=tag[xr]=tag[x];
			fh[xl]=minf[xl]+tag[x];fh[xr]=minf[xr]+tag[x];
			tag[x]=INF;
		}
	}
	inline void node(int x,int l,int r,int k){
		if(l==r){minf[x]=f[l-1];fh[x]=INF;return ;}
		pushdown(x);
		if(k<=mid) node(xl,l,mid,k);
		else node(xr,mid+1,r,k);
		pushup(x);
	}
	inline void section(int x,int l,int r,int L,int R,ll v){
		if(L<=l&&r<=R){fh[x]=minf[x]+v;tag[x]=v;return ;}
		pushdown(x);
		if(mid>=L) section(xl,l,mid,L,R,v);
		if(mid<R) section(xr,mid+1,r,L,R,v);
		pushup(x);
	}
	inline ll query(int x,int l,int r,int L,int R){
		if(L<=l&&r<=R) return fh[x];
		pushdown(x);
		ll sum=INF;
		if(mid>=L) sum=min(sum,query(xl,l,mid,L,R));
		if(mid<R) sum=min(sum,query(xr,mid+1,r,L,R));
		return sum;
	}
}qaq;

// ---------- SGT ---------- //

int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	rd(n);rd(len);
	for(re i=1;i<=n;++i){
		rd(h[i]),w[i]=h[i];s[i]=s[i-1]+w[i];
		while(tp&&h[i]>h[st[tp]]) --tp;
		if(tp) pre[i]=st[tp];
		st[++tp]=i;
	}
	qaq.build(1,1,n);
	for(re i=1;i<=n;++i){
		qaq.node(1,1,n,i);
		qaq.section(1,1,n,pre[i]+1,i,h[i]);
		int pos=lb(s+1,s+i+1,s[i]-len)-s;
		if(pos<i) f[i]=qaq.query(1,1,n,pos+1,i);
		else f[i]=f[i-1]+h[i];
	}
	wr(f[n]);puts("");
	return 0;
}

// ---------- Main ---------- //