src/dual_segtree.hpp

View this file on GitHub
Last update: 2025-10-07 04:08:36+09:00
Include: #include "src/dual_segtree.hpp"

Depends on

src/template.hpp

Verified with

src/test/aoj_DSL_2_D.cpp

Code

#pragma once
#include "template.hpp"

//伝搬一切しないver
template<class F, F (*id)(), void (*cmpo)(const F&, F&)> struct dual_segtree {
    dual_segtree(): dual_segtree(1) {}
    explicit dual_segtree(int n_): n(__bit_ceil(n_)), d(2 * n, id()) {}
    void apply(int l, int r, F f) {
        if(l == r) return;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) cmpo(f, d[l++]);
            if(r & 1) cmpo(f, d[--r]);
        }
    }
    F get(int i) {
        F r = id();
        for(i += n; i; i >>= 1) cmpo(d[i], r);
        return r;
    }
private:
    int n;
    vector<F> d;
};

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 3 "src/dual_segtree.hpp"

//伝搬一切しないver
template<class F, F (*id)(), void (*cmpo)(const F&, F&)> struct dual_segtree {
    dual_segtree(): dual_segtree(1) {}
    explicit dual_segtree(int n_): n(__bit_ceil(n_)), d(2 * n, id()) {}
    void apply(int l, int r, F f) {
        if(l == r) return;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if(l & 1) cmpo(f, d[l++]);
            if(r & 1) cmpo(f, d[--r]);
        }
    }
    F get(int i) {
        F r = id();
        for(i += n; i; i >>= 1) cmpo(d[i], r);
        return r;
    }
private:
    int n;
    vector<F> d;
};