区間最小遅延セグ木

segenttree seg(N) サイズNのセグ木を宣言 初期値INFなのでちゃんとしといてください

初期化まじでちゃんとしてください

range_add(l,r,x) lからrまでにxを加算

range_set(l,r,x) lからrまでをxに変更

query(l,r) lからrまでの最小値を出力

計算量　　全て logN

class segmenttree{
public:
    long long INF = 1e18;
    long long siz = 1;
    vector<long long> v;
    vector<long long> lazy_add;
    vector<long long> lazy_set;
    vector<bool> hav_set;
    segmenttree (long long n){
        siz = 1;
        while(siz < n)siz *= 2;
        v.assign(2*siz,INF);
        lazy_add.assign(2*siz,0);
        lazy_set.assign(2*siz,0);
        hav_set.assign(2*siz,false);
    }
    long long query(long long l,long long r){
        if(l > r)return INF;
        return query(l,r,1,0,siz-1);
    }
    void range_add(long long l,long long r,long long x){
        range_add(l,r,1,0,siz-1,x);
    }
    void range_set(long long l,long long r,long long x){
        range_set(l,r,1,0,siz-1,x);
    }
    void apply_set(long long s,long long x){
        v[s] = x;
        lazy_set[s] = x;
        lazy_add[s] = 0;
        hav_set[s] = true;
    }
    void apply_add(long long s,long long x){
        v[s] += x;
        if(hav_set[s]){
            lazy_set[s] += x;
        }
        else{
            lazy_add[s] += x;
        }

    }
    void push(long long s){
        if(hav_set[s]){
            apply_set(s*2,lazy_set[s]);
            apply_set(s*2+1,lazy_set[s]);
            hav_set[s] = false;
            lazy_set[s] = 0;
        }
        if(lazy_add[s]!=0){
            apply_add(s*2,lazy_add[s]);
            apply_add(s*2+1,lazy_add[s]);
            lazy_add[s] = 0;
        }
    }
    void pull(long long s){
        v[s] = min(v[s*2],v[s*2+1]);
    }
    long long query(long long L,long long R,long long s,long long l,long long r){
        if(r < L || l > R)return INF;
        if(l >= L && r <= R){
            return v[s];
        }
        push(s);
        long long ans = min(
            query(L,R,s*2,l,(l+r)/2),
            query(L,R,s*2+1,(l+r)/2+1,r)
        );
        return ans;
    }
    void range_set(long long L,long long R,long long s,long long l,long long r,long long x){
        if(r < L || l > R)return;
        if(l >= L && r <= R){
            apply_set(s,x);
            return;
        }
        push(s);
        range_set(L,R,s*2,l,(l+r)/2,x);
        range_set(L,R,s*2+1,(l+r)/2+1,r,x);
        pull(s);
    }
    void range_add(long long L,long long R,long long s,long long l,long long r,long long x){
        if(r < L || l > R)return;
        if(l >= L && r <= R){
            apply_add(s,x);
            return;
        }
        push(s);
        range_add(L,R,s*2,l,(l+r)/2,x);
        range_add(L,R,s*2+1,(l+r)/2+1,r,x);
        pull(s);
    } 
};