fork download

copy

#include <bits/stdc++.h>
 
struct S { ... }; // Segment tree element type
const S e = ...; // The identity element
S op(S a, S b) { ... } // Compute a · b
 
struct F { ... }; // Lazy mapping type
const F id = ...; // The identity mapping
S mapping(F f, S x) { ... } // Compute f(x)
F composition(F f, F g) { ... } // Compute f ∘ g
F inv(F f) { ... } // Compute f^(-1)
 
class lazy_segtree {
    public:
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = 1; log = 0;
        while (size < _n) size *= 2, log++;
        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--) d[i] = op(d[2 * i], d[2 * i + 1]);
    }
 
    S prod(int l, int r) const { // const!!!
        return prod(1, 0, size, id, l, r);
    }
 
    void apply(int l, int r, F f) {
        apply(1, 0, size, id, l, r, f);
    }
 
    public:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;
 
    void update(int k) { d[k] = mapping(lz[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]);
    }
 
    S prod(int k, int cl, int cr, F g, int l, int r) const { // const!!!
        if (l <= cl && cr <= r) return mapping(g, d[k]);
 
        int cm = (cl + cr) / 2;
        F h = composition(g, lz[k]);
        if (r <= cm) return prod(2 * k, cl, cm, h, l, r);
        if (l >= cm) return prod(2 * k + 1, cm, cr, h, l, r);
        return op(prod(2 * k, cl, cm, h, l, r),
                  prod(2 * k + 1, cm, cr, h, l, r));
    }
 
    void apply(int k, int cl, int cr, F g, int l, int r, F f) {
        if (l <= cl && cr <= r) {
            all_apply(k, composition(inv(g), composition(f, g)));
            return;
        }
 
        int cm = (cl + cr) / 2;
        F h = composition(g, lz[k]);
        if (r <= cm) 
            apply(2 * k, cl, cm, h, l, r, f);
        else if (l >= cm)
            apply(2 * k + 1, cm, cr, h, l, r, f);
        else {
            apply(2 * k, cl, cm, h, l, r, f);
            apply(2 * k + 1, cm, cr, h, l, r, f);
        }
        update(k);
    }
};

prog.cpp:3:12: error: expected unqualified-id before ‘...’ token
 struct S { ... }; // Segment tree element type
            ^~~
prog.cpp:4:13: error: expected primary-expression before ‘...’ token
 const S e = ...; // The identity element
             ^~~
prog.cpp: In function ‘S op(S, S)’:
prog.cpp:5:18: error: expected primary-expression before ‘...’ token
 S op(S a, S b) { ... } // Compute a · b
                  ^~~
prog.cpp:5:22: warning: no return statement in function returning non-void [-Wreturn-type]
 S op(S a, S b) { ... } // Compute a · b
                      ^
prog.cpp: At global scope:
prog.cpp:7:12: error: expected unqualified-id before ‘...’ token
 struct F { ... }; // Lazy mapping type
            ^~~
prog.cpp:8:14: error: expected primary-expression before ‘...’ token
 const F id = ...; // The identity mapping
              ^~~
prog.cpp: In function ‘S mapping(F, S)’:
prog.cpp:9:23: error: expected primary-expression before ‘...’ token
 S mapping(F f, S x) { ... } // Compute f(x)
                       ^~~
prog.cpp:9:27: warning: no return statement in function returning non-void [-Wreturn-type]
 S mapping(F f, S x) { ... } // Compute f(x)
                           ^
prog.cpp: In function ‘F composition(F, F)’:
prog.cpp:10:27: error: expected primary-expression before ‘...’ token
 F composition(F f, F g) { ... } // Compute f ∘ g
                           ^~~
prog.cpp:10:31: warning: no return statement in function returning non-void [-Wreturn-type]
 F composition(F f, F g) { ... } // Compute f ∘ g
                               ^
prog.cpp: In function ‘F inv(F)’:
prog.cpp:11:14: error: expected primary-expression before ‘...’ token
 F inv(F f) { ... } // Compute f^(-1)
              ^~~
prog.cpp:11:18: warning: no return statement in function returning non-void [-Wreturn-type]
 F inv(F f) { ... } // Compute f^(-1)
                  ^

Standard output is empty