mkreem_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub mkr33m/mkreem_library

:warning: b, a+b, ..., (r-l)a + b を加算
(DataStructure/LazySegtree_arith_add.hpp)

Depends on

Code

#ifndef LazySegtree_arith_add_HPP
#define LazySegtree_arith_add_HPP

#include <vector>
#include "../Others/macros.hpp"
#include "../ac-library/atcoder/lazysegtree.hpp"

namespace arith_add {

struct S {
    ll sum;
    int l, r;
};
S op(S L, S R) {
    return S{L.sum + R.sum, std::min(L.l, R.l), std::max(L.r, R.r)};
}
S e() {
    return S{0LL, INF, -INF};
}
struct F {
    ll a, b;
};
S mapping(F f, S s) {
    return S{
        s.sum + (f.a * (s.l + s.r - 1) + f.b * 2) * (s.r - s.l) / 2,
        s.l, s.r
        };
}
F composition(F f, F g) {
    return {f.a + g.a, f.b + g.b};
};
F id() {
    return F{0, 0};
}

using lazy = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;

template <typename T>
struct LazySegtree_arith : lazy {
    using lazy::lazy; // 基底クラスが持つ全コンストラクタを、派生クラスでも使えるようにする
    LazySegtree_arith(int N) {
        std::vector<S> vec(N);
        for (int i = 0; i < N; i++) {
            vec[i] = S{0, i, i + 1};
        }
        LazySegtree_arith tmp(vec); // using lazy::lazy による、acl の遅延セグ木のコンストラクタを呼び出している
        /**
         * 派生クラスにおいて、int N だけ渡して中身はゼロ初期化、vector<ll> を渡して vector<S> に変換してから初期化、など、別の引数パターンでコンストラクタを定義したい。
         * しかし、派生クラスでもわざわざセグ木を構築するのは面倒 → 基底クラスのコンストラクタを呼び出してセグ木を構築して（一時オブジェクトの生成。重い初期化を基底クラスに丸投げ）、その一時オブジェクトを *this にコピー。
         */
        (*this) = tmp;
    }
    LazySegtree_arith(std::vector<T> v) {
        std::vector<S> vec((int)v.size());
        for (int i = 0; i < (int)v.size(); i++) {
            vec[i] = S{v[i], i, i + 1};
        }
        LazySegtree_arith tmp(vec);
        (*this) = tmp;
    }

    /**
     * @brief b, a+b, ..., (r-l)a + b を加算
     */
    void apply(int l, int r, F f) {
        lazy::apply(l, r, F{f.a, f.b - f.a * get(l).l});
    }
    /**
     * @brief la + b, (l+1)a + b, ..., (r-1)a + b を加算
     */
    void apply_idx(int l, int r, F f) {
        lazy::apply(l, r, f);
    }
};

} // namespace arith_add

#endif // LazySegtree_arith_add_HPP
#line 1 "DataStructure/LazySegtree_arith_add.hpp"



#include <vector>
#line 1 "Others/macros.hpp"



#line 5 "Others/macros.hpp"
#include <queue>
#include <cmath>

using ll = long long;
using lll = __int128_t;
using ld = long double;
#define newl '\n'
#define REF const auto&
#define INF 1000390039
#define LLINF 1000000039000000039
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LLMAX LONG_LONG_MAX
#define LLMIN LONG_LONG_MIN
#define BIT(i) (1LL << (i))
#define tbit(n, k) ((n >> k) & 1) // nの（上から）kビット目
#define bit(n, k) (n & (1LL << (k))) // nの（下から）kビット目
#define PI acos(-1)
#define inr(l, x, r) (l <= x && x < r)
#define einr(l, x, r) (l <= x && x <= r)
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define erep(i, a, b) for(int i = (a); i <= (b); i++)
#define rrep(i, a, b) for(int i = (a); i >= (b); i--)
#define repl(i, a, b) for(long long i = (a); i < (b); i++)
#define erepl(i, a, b) for(long long i = (a); i <= (b); i++)
#define rrepl(i, a, b) for(long long i = (a); i >= (b); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define FOR_subset(sub, bit) for (ll sub = (bit); sub >= 0; sub = (sub == 0 ? -1 : (sub - 1) & (bit)))
#define UNIQUE(v) (std::sort(all(v)), (v).erase(std::unique(all(v)), (v).end()))
#define pcnt(x) __builtin_popcount(x)
#define llpcnt(x) __builtin_popcountll(x)
#define VC(name, type, ...) vector<type> name(__VA_ARGS__)
#define VVC(name, type, a, ...) vector<vector<type>> name(a, vector<type>(__VA_ARGS__))
#define VVVC(name, type, a, b, ...) vector<vector<vector<type>>> name(a, vector<vector<type>>(b, vector<type>(__VA_ARGS__)))
#define VVVVC(name, type, a, b, c, ...) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(__VA_ARGS__))))
#define VVVVVC(name, type, a, b, c, d, ...) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(__VA_ARGS__)))));
template <typename T>
int lwb(const std::vector<T>& vec, const T& x){
    return lower_bound(all(vec), x) - vec.begin();
}
template <typename T>
int upb(const std::vector<T>& vec, const T& x){
    return upper_bound(all(vec), x) - vec.begin();
}
template <typename T>
T max(const std::vector<T>& vec){ return *max_element(all(vec)); }
template <typename T>
T min(const std::vector<T>& vec){ return *min_element(all(vec)); }
template <typename T>
T rad(const T& x){ return x * PI/180; }
template <typename T>
using maxpq = std::priority_queue<T>;
template <typename T>
using minpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;
// 最大値・最小値の更新
template <typename T1, typename T2>
bool chmax(T1 &a, const T2& b){
    if (a < b) { a = b; return 1; }
    return 0;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2& b){
    if (a > b) { a = b; return 1; }
    return 0;
}

const int di4[4] = {-1, 0, 1, 0};
const int dj4[4] = {0, 1, 0, -1};
const int di8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int dj8[8] = {0, 1, 1, 1, 0, -1, -1, -1};

bool out_of_grid(const int& i, const int& j, const int& h, const int& w){
    if(i < 0 || j < 0 || i >= h || j >= w) return true;
    return false;
}


#line 1 "ac-library/atcoder/lazysegtree.hpp"



#include <algorithm>
#line 1 "ac-library/atcoder/internal_bit.hpp"



#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder


#line 6 "ac-library/atcoder/lazysegtree.hpp"
#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP
#endif
#include <cassert>
#include <functional>
#line 12 "ac-library/atcoder/lazysegtree.hpp"

namespace atcoder {

#if __cplusplus >= 201703L

template <class S,
          auto op,
          auto e,
          class F,
          auto mapping,
          auto composition,
          auto id>
struct lazy_segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");
    static_assert(
        std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
        "mapping must work as S(F, S)");
    static_assert(
        std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
        "composition must work as F(F, F)");
    static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
                  "id must work as F()");

#else

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {

#endif

  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder


#line 7 "DataStructure/LazySegtree_arith_add.hpp"

namespace arith_add {

struct S {
    ll sum;
    int l, r;
};
S op(S L, S R) {
    return S{L.sum + R.sum, std::min(L.l, R.l), std::max(L.r, R.r)};
}
S e() {
    return S{0LL, INF, -INF};
}
struct F {
    ll a, b;
};
S mapping(F f, S s) {
    return S{
        s.sum + (f.a * (s.l + s.r - 1) + f.b * 2) * (s.r - s.l) / 2,
        s.l, s.r
        };
}
F composition(F f, F g) {
    return {f.a + g.a, f.b + g.b};
};
F id() {
    return F{0, 0};
}

using lazy = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;

template <typename T>
struct LazySegtree_arith : lazy {
    using lazy::lazy; // 基底クラスが持つ全コンストラクタを、派生クラスでも使えるようにする
    LazySegtree_arith(int N) {
        std::vector<S> vec(N);
        for (int i = 0; i < N; i++) {
            vec[i] = S{0, i, i + 1};
        }
        LazySegtree_arith tmp(vec); // using lazy::lazy による、acl の遅延セグ木のコンストラクタを呼び出している
        /**
         * 派生クラスにおいて、int N だけ渡して中身はゼロ初期化、vector<ll> を渡して vector<S> に変換してから初期化、など、別の引数パターンでコンストラクタを定義したい。
         * しかし、派生クラスでもわざわざセグ木を構築するのは面倒 → 基底クラスのコンストラクタを呼び出してセグ木を構築して（一時オブジェクトの生成。重い初期化を基底クラスに丸投げ）、その一時オブジェクトを *this にコピー。
         */
        (*this) = tmp;
    }
    LazySegtree_arith(std::vector<T> v) {
        std::vector<S> vec((int)v.size());
        for (int i = 0; i < (int)v.size(); i++) {
            vec[i] = S{v[i], i, i + 1};
        }
        LazySegtree_arith tmp(vec);
        (*this) = tmp;
    }

    /**
     * @brief b, a+b, ..., (r-l)a + b を加算
     */
    void apply(int l, int r, F f) {
        lazy::apply(l, r, F{f.a, f.b - f.a * get(l).l});
    }
    /**
     * @brief la + b, (l+1)a + b, ..., (r-1)a + b を加算
     */
    void apply_idx(int l, int r, F f) {
        lazy::apply(l, r, f);
    }
};

} // namespace arith_add
Back to top page