Segment Tree with Lazy Propagation, I added the LazyNode struct

segmentTreeWithLazy.cpp

// Planchota con modificaciones de Josue
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <cctype>
#define me(x,a) memset(x,a,sizeof(x))
#define FN(a,n) for(int a=0;a<n;a++)
#define FOR(a,ini,fin) for(int a=(ini);a<(fin);a++)
#define ull unsigned long long
#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d %d",&x,&y)
#define sc3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define all(v) v.begin(),v.end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define endl "\n"
#define MAXN 100005
using namespace std;


struct LazyNode{
	int s;
	LazyNode()
	{
		//valor o elemento neutro:
		s = 0;
	}
	void operator +=(const LazyNode &nl)
	{
		s += nl.s;
	}
	bool esNeutro(){ //puede reemplazarse usando un flag para cada LazyNode
		return s == 0;
	}
};

struct Node{
    int val;
    int ind;
    Node(){
        //valor o elemento neutro:
        val = INT_MAX;
        ind = 100000;
    }
	void operator +=(const LazyNode &nl) 
	{
		val += nl.s;
	}
};

int inih[100005];

Node operator +( const Node &a , const Node &b ){
    Node c=a;
    if(a.val > b.val) {
    	c = b;
    }
    return c;
}
//notese la diferencia con BIT en el cual para consultar un rango (no solo acumulados) se requiere de la operacion resta, en cambio en ST no.
struct ST{
    Node T[ MAXN * 4 ];
    LazyNode LazyT[ MAXN * 4 ];
    int n;
    ST(){}
    ST( int sz ){
        //cout << "INIT" << endl;
        n = sz;
        build_tree( 0 , 0 , sz - 1 );
        //cout << "INIT" << endl;
    }
    void build_tree( int node , int a , int b ){
        if( a == b ){
            LazyT[ node ] = LazyNode();
            

            //inicializando el elemento 'a'
            T[ node ].val = inih[a] ;
            T[ node ].ind = a;

            return;
        }
        build_tree( ((node<<1) + 1) , a , ((a+b)>>1) ) , build_tree( ((node<<1) + 2) , ((a+b)>>1) + 1  , b );
        T[ node ] = T[ ((node<<1) + 1) ] + T[ ((node<<1) + 2) ];
    }
    void push( int node , int a , int b ){
        if( LazyT[ node ].esNeutro() ) return;
        
        T[ node ] += LazyT[ node ];
        if( a != b ){
            LazyT[ node*2 + 1 ] += LazyT[ node ]; 
			LazyT[ node*2 + 2 ] += LazyT[ node ]; 
        }
        
        LazyT[ node ] = LazyNode();
    }
    Node query( int node , int a , int b , int lo , int hi ){
        push( node , a , b );
        if( lo > b || a > hi ) return Node();
        if( a >= lo && hi >= b ) return T[ node ];
        return query( ((node<<1) + 1) , a , ((a+b)>>1) , lo , hi ) + query( ((node<<1) + 2) , ((a+b)>>1) + 1  , b , lo , hi );
    }
    void update( int node , int a , int b , int lo , int hi, const LazyNode& val){ 

        push( node , a , b );
        if( lo > b || a > hi ) return ;
        if( a >= lo && hi >= b ) {
            LazyT[ node ] = val;
            push( node , a , b );
            return;
        }
        update( ((node<<1) + 1) , a , ((a+b)>>1) , lo , hi , val);
        update( ((node<<1) + 2) , ((a+b)>>1) + 1  , b , lo , hi , val);
        T[ node ] = T[ ((node<<1) + 1) ] + T[ ((node<<1) + 2) ] ;
    }
    Node query( int lo , int hi ){
        //cout << "QUERY " << lo << " " << hi << endl;
        return query( 0 , 0 , n - 1 , lo , hi );

    }
    void update( int lo , int hi ,const LazyNode& val){
        //cout << lo << " " << hi << endl;
        update( 0 , 0 , n - 1 , lo , hi , val );
    }
}st;

int main()
{
	int n,m,w;
	while( sc3(n,m,w) == 3 )
	{
		FN(i,n)
		{
			sc1(inih[i]);
		}
		st= ST(n);
		LazyNode ln;
		ln.s = 1;
		FN(i,m)
		{
			Node node ;
			node = st.query(0, n-1);
			st.update(node.ind, min(node.ind + w - 1 , n - 1 ) , ln );
		}
		Node node = st.query(0, n-1);
		printf("%d\n",node.val);
	}
}