****D. Strip( seg tree + b seach or seg tree+ bsearch + dp)

B. Strip

another similar problem is   sofi and array  which is included is also in the blog

Alexandra has a paper strip with n numbers on it. Let's call them ai from left to right.

Now Alexandra wants to split it into some pieces (possibly 1). For each piece of strip, it must satisfy:

• Each piece should contain at least l numbers.
• The difference between the maximal and the minimal number on the piece should be at most s.

Please help Alexandra to find the minimal number of pieces meeting the condition above.

Input

The first line contains three space-separated integers n, s, l (1 ≤ n ≤ 105, 0 ≤ s ≤ 109, 1 ≤ l ≤ 105).

The second line contains n integers ai separated by spaces ( - 109 ≤ ai ≤ 109).

Output

Output the minimal number of strip pieces.

If there are no ways to split the strip, output -1.

Sample test(s)

input

7 2 2
1 3 1 2 4 1 2

output

3

input

7 2 2
1 100 1 100 1 100 1

output

-1

Note

For the first sample, we can split the strip into 3 pieces: [1, 3, 1], [2, 4], [1, 2].

For the second sample, we can't let 1 and 100 be on the same piece, so no solution exists.

----------------------------------EDITORIAL-------------------------------

THIS PROBLEM CAN BE SOLVE IN MANY WAYS 

I  HAVE USED SEGMENT TREE + BINARY SEARCH APPROACH ..

1st we will calculate if ans exists than what will be the minimum no of segments we required ..

start from the first element of the  array and add as much element as possible if it satisfy the property that max-min of 

of the set must be <=diff(a given value)

if any element fails to satisfy this condition than start a new group from that element ...

after doing this if all groups formed have no of elements >L, than answer will be the no of groups ,

but what  if size of some groups are <L than we need to add some elements in that group, from where we add elements to that group , obviously not from the right since  first element in the right group fails to satisfy the  condition max-min<=d  so it is not in this group ,,

now come to main property of this problem ,

if a segment of length 'l'  to  'r'  satisfy the condition than a segment  'l' to 'r-1'  will also satisfy the  conditions , see how?

 since we are removing a element  from the group 

soo 

case1- that element is neither min not max element of that group that obviously removing it does not cause any problem.

case2- that element will be the max element of that group , than in that case after removing that element  max value of that group will be either less than of equal to that element 

soo again it will not fail condition max-min<=d( since decreasing max value give much less diff)

case 3- that element will be the min element of that group , than in that case after removing that element  min  value of that group will be either greater than of equal to that element soo again it will not fail condition max-min<=d

( since increasing min value give much less diff)

now coming to problem how to solve it , 

1st of all we have made groups 

now start from the 1st group this group will must contain atleast L elements try to give at most element element to its adjecent right group , we can fix this how many element can be added to the next group with the help of binary search ,

suppose the start of next group is from element no 7 and 1st group can give elements from index 3 to 6  so next group can include element at index 3,4,5,6 to its group 

how to fix it how many element it can include ?

as we have discussed the property that if a group can form from l to r than it can also form from l to r-1 also 

so we can fix index including using binary search 

initially we check whether we can include  index 5,6 or not if it can include 5 to 6 that we do binary search in  range 3 to 4 to include more elements ... and so on ,

now how to check whether  we can include a range x to y in the  the group having range  x+1 to z ?

it is very easy .

we just check min and max in the range x to z and if there difference <=d than we can include it ..

if any of the group after this all operation have size <L

than ans will be -1 else ans will be initial group count 

--------------------------------code------------------------------------

#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
lli arr[110000];
lli tree1[600000],tree2[600000];
#define inf 9999999999
lli query1(lli node,lli start,lli end,lli r1,lli r2)
 {
   //cout<<" minq  index "<<node<<endl;
    if(start>end || r1>end || r2<start) return  inf;
    if(r1<=start && r2>=end)
    {
      return tree1[node]; 
    }
    
    else
    {
     lli q1=query1(2*node,start,(start+end)/2,r1,r2);
      lli q2= query1(2*node+1,((start+end)/2)+1,end,r1,r2);
    return min(q1,q2);
    }
 }
 
 
 lli query2(lli node,lli start,lli end,lli r1,lli r2)
 {
   //cout<<" minq  index "<<node<<endl;
    if(start>end || r1>end || r2<start) return  -inf;
    if(r1<=start && r2>=end)
    {
      return tree2[node]; 
    }
    
    else
    {
     lli q1=query2(2*node,start,(start+end)/2,r1,r2);
      lli q2= query2(2*node+1,((start+end)/2)+1,end,r1,r2);
    return max(q1,q2);
    }
 }
 



 
 void build2(lli node , lli start,lli end)
 {
  if(start==end) tree2[node]=arr[start];
  else if(start>end) return ;
  else
   {
    build2(2*node,start,(start+end)/2);
    build2(2*node+1,((start+end)/2)+1,end);
    tree2[node]=max(tree2[2*node],tree2[2*node+1]);
   }
   
 }
 
 void build1(lli node , lli start,lli end)
 {

  if(start==end) tree1[node]=arr[start];
  else if(start>end) return ;
  else
   {
    build1(2*node,start,(start+end)/2);
    build1(2*node+1,((start+end)/2)+1,end);
   //  cout<<" start "<<start<<" end "<<end<<" min "<<min(tree1[2*node],tree1[2*node+1])<<endl;
    tree1[node]=min(tree1[2*node],tree1[2*node+1]);
   }
   
 }
 
 
int main()
 {
  lli n,d,ll;
   cin>>n>>d>>ll;
   
   for(lli i=0;i<n;i++)
    {
      cin>>arr[i];
    }
    build1(1,0,n-1);
    build2(1,0,n-1);
    // cout<<" build done "<<endl;
 vector<pair<lli,lli> > v;
 for(lli i=0;i<n;)
  {
   lli mini=inf;
   lli maxi=-inf;
   lli j;
   for(j=i;j<n;j++)
    {
     if(arr[j]>maxi) maxi=arr[j];
     if(arr[j]<mini) mini=arr[j];
     if(maxi-mini>d) break;
   } 
   v.push_back({i,j-1});
    
   i=j;
  }
  lli sz=v.size();
  if(v[0].second-v[0].first+1<ll)
    {
      cout<<-1<<endl;
      return 0;
    }
    
    
   for(lli i=1;i<sz;i++)
    {
         lli l=v[i-1].first+ll;
         lli r=v[i].second;
         // cout<<" ini "<<l<<" "<<r<<endl;
         lli mid=r;
         lli tt=mid;
         
         while(l<r)
          {
            mid=(l+r)/2;
           
           lli min=query1(1,0,n-1,mid,r);
            //cout<<" min done "<<min<<endl;
           lli max=query2(1,0,n-1,mid,r);
            //cout<<" mid "<<mid<<" maxi "<<max<<" min "<<min<<endl;
           if(max-min>d)
           {
            l=mid+1;
    }
    else
    {
     tt=mid;
     r=mid;
     
    }
    }
       
       if(v[i].second-tt+1<ll)
        {
          cout<<-1<<endl;
          exit(0);
   }
   else
   {
     //cout<<" set left "<<tt<<endl;
    v[i].first=tt;
   }
       
    }
    cout<<sz<<endl;
 }

-------------------------------we can solve this problem using 

seg tree + bsearch + dp but for that we need to create a segtree for dp also ------------------------------------------

see this

#include <bits/stdc++.h>

using namespace std;
#define INF 2000000000
struct seg
{
 int mi,mx;
}tree[1000006];
int arr[200010];
int T[600010];
int dp[200010];
void build(int node,int st,int en)
{
 if(st>en) return;
 if(st==en) {
 tree[node].mi=arr[st],tree[node].mx=arr[st];return;}
 else
 {
  int m=(st+en)/2;
  build(2*node,st,m);
  build(2*node+1,m+1,en);
  tree[node].mi=min(tree[2*node].mi,tree[2*node+1].mi);
  tree[node].mx=max(tree[2*node].mx,tree[2*node+1].mx);
 } 
}

struct seg query(int node,int st,int en,int lo,int hi)
{
 if(st>en||st>hi||en<lo)
 {
  seg temp;
  temp.mi=INF;
  temp.mx=-INF;
  return temp;
 }
 
 if(st>=lo&&en<=hi)
 {
  return tree[node];
 }
 int m=(st+en)/2;
 seg q1=query(2*node,st,m,lo,hi);
 seg q2=query(2*node+1,m+1,en,lo,hi);
 
 seg q;
 q.mx=max(q1.mx,q2.mx);
 q.mi=min(q1.mi,q2.mi);
 
 return q;
}

void bld(long v,long tl,long tr)
{
 if (tl==tr)
 {
  T[v]=dp[tl];
  return ;
 }
 long tm=tl+tr;
 tm/=2;
 bld(v*2,tl,tm);
 bld(v*2+1,tm+1,tr);
 T[v]=min(T[v*2],T[v*2+1]);
}

int ct=0;
long q1(long v,long tl,long tr,long l,long r)
{
 //cout<<"l "<<" r "<<l<<" "<<r<<endl;
   if (l>r)return 1e9;
    if (tl==l&&tr==r)
     return T[v];
    long tm=tl+tr;
   tm/=2;
 long p1,p2;
 p1=q1(v*2,tl,tm,l,min(r,tm));
 p2=q1(v*2+1,tm+1,tr,max(l,tm+1),r);
 //cout<<min(p1,p2)<<endl;
 return min(p1,p2);
 
}

void update(int node,int st,int en,int lo,int hi,int val)
{
 if(st>en||st>hi||en<lo)
 {
  return;
 }
 if(st>=lo&&en<=hi)
 {
  T[node]=val;return;
 }
 int m=(st+en)/2;
 update(2*node,st,m,lo,hi,val);
 update(2*node+1,m+1,en,lo,hi,val);
 
 T[node]=min(T[2*node],T[2*node+1]);
 
}


 
int main()
{
 int n,len,s;
 cin>>n>>s>>len;
 
 for(int i=1;i<=n;i++)
 {
  cin>>arr[i];
 }
for (int i=1;i<=n;i++)
 dp[i]=1e9;
 bld(1,0,n);
  
 //cout<<T[n]<<endl;
 build(1,1,n);
 int mid;
 for(int i=1;i<=n;i++)
 {
   if(i<len)
   continue;
  int l=1;
  int r=i-len+1;
//  int lft=l;
  while(l<r)
  {
   //cout<<l<<" "<<r<<" "<<mid<<endl;;
    mid=(l+r)/2;
    seg tmp=query(1,1,n,mid,i);
    if(tmp.mi+s<tmp.mx)
    l=mid+1;
    else
    {
     
//          lft=mid;
    r=mid;
    }
  }
  seg tmp;
 // cout<<"lefts "<<i<<" "<<l<<endl;
  tmp=query(1,1,n,l,i);
  if(tmp.mi+s<tmp.mx)
  continue;
 // cout<<"i l "<<i<<" "<<l<<endl;
     int res=q1(1,0,n,l-1,i-len);
    
  // cout<<"res "<<res<<endl;
  update(1,0,n,i,i,res+1);
 }
 int qq=INF;
 qq=q1(1,0,n,n,n);
 if(qq>=1000000)
 cout<<-1<<endl;
 else cout<<qq<<endl;
 
 return 0;
}