虚拟参赛的时候没想到是线段树，看到很多人都过了，也蛮着急的。
首先用二分+线段树的方法更新DP[i]：它表示以A[i]为结尾可以最前到哪个位置；
再用线段树计算ans[i]：它表示当前i个A元素可以最少分成多少个pieces，ans[i]=1+min(ans[j])，dp[i]-1<=j<=i-L。
over.
#define N 100000+5 int a[N],dp[N],Ans[N];
struct segment {
int l,r;
int Min,Max,ans;
} seg[*N]; struct diff {
int Max,Min;
diff(int x=,int n=):Max(x),Min(n) {}
}; void build(int p,int l,int r)
{
seg[p].l=l, seg[p].r=r, seg[p].ans=-;;
if (l==r) {
seg[p].Min = seg[p].Max = a[l];
return;
}
build(p<<,l,(l+r)>>);
build((p<<)+,((l+r)>>)+,r); seg[p].Min = min(seg[p<<].Min, seg[(p<<)+].Min),
seg[p].Max = max(seg[p<<].Max, seg[(p<<)+].Max);
} diff query1(int p,int l,int r)
{
if (l<=seg[p].l && seg[p].r<=r) {
return diff(seg[p].Max,seg[p].Min);
} diff t1,t2;
bool f1=false, f2=false;
if (seg[p<<].r>=l)
f1=true, t1=query1(p<<,l,r);
if (seg[(p<<)+].l<=r)
f2=true, t2=query1((p<<)+,l,r); if (f1) {
if (f2)
return diff(max(t1.Max,t2.Max), min(t1.Min,t2.Min));
else
return t1;
}
else
if (f2)
return t2;
return diff(,);
} int query2(int p,int l,int r)
{
if (l<=seg[p].l && seg[p].r<=r) {
return seg[p].ans;
} int t1=-,t2=-;
if (seg[p<<].r>=l)
t1=query2(p<<,l,r);
if (seg[(p<<)+].l<=r)
t2=query2((p<<)+,l,r); if (t1==-) {
return t2;
}
else {
if (t2==-)
return t1;
else return min(t1,t2);
} } void add(int p,int i,int newans)
{
if (seg[p].l==seg[p].r) {
seg[p].ans=newans;
return;
} if (i<=seg[p<<].r)
add(p<<,i,newans);
else
add((p<<)+,i,newans); if (seg[p<<].ans==-) {
seg[p].ans = seg[(p<<)+].ans;
}
else {
if (seg[(p<<)+].ans==-)
seg[p].ans=seg[p<<].ans;
else
seg[p].ans=min(seg[p<<].ans,seg[(p<<)+].ans);
}
} int main()
{
//freopen("b.txt","r",stdin); int n,s,l;
cin>>n>>s>>l;
for (int i=;i<=n;i++) scanf("%d",&a[i]);
build(,,n);
for (int i=;i<=n;i++) {
int L=,R=i-;
dp[i]=i;
while (L<=R) {
int mid = (L+R)>>;
diff tmp = query1(,mid,i);
if (tmp.Max-tmp.Min<=s) {
R=mid-;
dp[i]=mid;
}
else {
L=mid+;
}
}
} for (int i=;i<=n;i++) {
if (i<l) {
Ans[i]=-;
continue;
}
int tmp=-;
if (i-l> && dp[i]-<=i-l)
tmp=query2(,max(,dp[i]-),i-l);
if (dp[i]==) tmp=; if (tmp==-)
Ans[i]=-;
else
Ans[i]=tmp+, add(,i,Ans[i]);
}
cout<<Ans[n]<<endl; return ;
}