fork download

copy

ll sq_f(ll x) {
    long double r = sqrt((long double)x);
    ll y = (ll)r;
    while ((y + 1) > 0 && (y + 1) * (y + 1) <= x) ++y;
    while (y * y > x) --y;
    return y;
}
 
// 1-based indexing
struct Lazy_Segment_Tree {
    struct Node {
        ll val, lazy, mn, mx;
        Node(ll _val = 0, ll _lazy = 0, ll _mn = 0, ll _mx = 0) : val(_val), lazy(_lazy), mn(_mn), mx(_mx) {}
        Node operator=(ll _val) {
            val = _val;
            lazy = 0;
            mn = mx = 0;
            return *this;
        }
    };
 
    int size, n;
    vector<Node> tree;
    vector<vector<ll>> pref;
 
    void init(int n_) {
        n = n_;
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size + 5, Node());
        pref.resize(6);
        for (int s = 0; s < 6; s++) pref[s].assign(size + 1, 0);
    }
 
    Node merge(const Node &a, const Node &b) {
        Node res;
        res.val = a.val + b.val;
        res.lazy = 0;
        res.mn = min(a.mn, b.mn);
        res.mx = max(a.mx, b.mx);
        return res;
    }
 
    ll range_stage_sum(int s, int l, int r) {
        return pref[s][r] - pref[s][l - 1];
    }
 
    void apply(int idx, int lx, int rx, ll delta) {
        tree[idx].mn += delta;
        tree[idx].mx += delta;
        tree[idx].lazy += delta;
 
        if (tree[idx].mn < 0) tree[idx].mn = 0;
        if (tree[idx].mx < 0) tree[idx].mx = 0;
 
        if (tree[idx].mn >= 5) {
            tree[idx].val = (rx - lx + 1);
            return;
        }
        if (tree[idx].mn == tree[idx].mx) {
            int stage = (int)tree[idx].mn;
            if (stage > 5) stage = 5;
            tree[idx].val = range_stage_sum(stage, lx, rx);
        }
    }
 
    void push(int idx, int lx, int rx) {
        if (tree[idx].lazy == 0) return;
        if (lx != rx) {
            int mx = (lx + rx) / 2;
            apply(2 * idx, lx, mx, tree[idx].lazy);
            apply(2 * idx + 1, mx + 1, rx, tree[idx].lazy);
        }
        tree[idx].lazy = 0;
    }
 
    void build(int idx, int lx, int rx) {
        tree[idx].lazy = 0;
        if (lx == rx) {
            tree[idx].mn = tree[idx].mx = 0;
            tree[idx].val = (lx <= n ? range_stage_sum(0, lx, rx) : 0);
            return;
        }
        int mx = (lx + rx) / 2;
        build(2 * idx, lx, mx);
        build(2 * idx + 1, mx + 1, rx);
        tree[idx] = merge(tree[2 * idx], tree[2 * idx + 1]);
    }
 
    void build(const vector<vector<ll>> &vals) {
        for (int s = 0; s < 6; s++) pref[s][0] = 0;
        for (int i = 1; i <= size; i++) {
            for (int s = 0; s < 6; s++) {
                pref[s][i] = pref[s][i - 1] + (i <= n ? vals[s][i] : 0LL);
            }
        }
        build(1, 1, size);
    }
 
    void update(int l, int r, ll v, int idx, int lx, int rx) {
        if (rx < l || lx > r) return;
 
        if (l <= lx && rx <= r) {
            if (tree[idx].mn == tree[idx].mx) {
                apply(idx, lx, rx, v);
                return;
            }
            if (tree[idx].mn + v >= 5) {
                apply(idx, lx, rx, v);
                return;
            }
        }
 
        if (lx == rx) {
            apply(idx, lx, rx, v);
            if (tree[idx].mn >= 5) tree[idx].val = 1;
            else tree[idx].val = range_stage_sum((int)tree[idx].mn, lx, rx);
            return;
        }
 
        push(idx, lx, rx);
        int mx = (lx + rx) / 2;
        update(l, r, v, 2 * idx, lx, mx);
        update(l, r, v, 2 * idx + 1, mx + 1, rx);
        tree[idx] = merge(tree[2 * idx], tree[2 * idx + 1]);
    }
 
    void update(int l, int r, ll v) { update(l, r, v, 1, 1, size); }
 
    ll query(int l, int r, int idx, int lx, int rx) {
        if (rx < l || lx > r) return 0;
 
        if (l <= lx && rx <= r) {
            if (tree[idx].mn >= 5) return (rx - lx + 1);
            if (tree[idx].mn == tree[idx].mx) {
                int stage = (int)tree[idx].mn;
                if (stage > 5) stage = 5;
                return range_stage_sum(stage, lx, rx);
            }
        }
 
        if (lx == rx) {
            if (tree[idx].mn >= 5) return 1;
            int stage = (int)tree[idx].mn;
            if (stage > 5) stage = 5;
            return range_stage_sum(stage, lx, rx);
        }
 
        push(idx, lx, rx);
        int mx = (lx + rx) / 2;
        return query(l, r, 2 * idx, lx, mx) + query(l, r, 2 * idx + 1, mx + 1, rx);
    }
 
    ll query(int l, int r) { return query(l, r, 1, 1, size); }
};
 
void solve() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
 
    vector<vector<ll>> vals(6);
    for (int s = 0; s < 6; s++) vals[s].assign(n + 1, 0);
 
    for (int i = 1; i <= n; i++) {
        vals[0][i] = a[i];
        for (int s = 1; s < 6; s++) vals[s][i] = sq_f(vals[s - 1][i]);
    }
 
    Lazy_Segment_Tree st;
    st.init(n);
    st.build(vals);
 
    int q;
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int l, r;
            cin >> l >> r;
            st.update(l, r, 1);
        } else if (type == 2) {
            int l, r, k;
            cin >> l >> r >> k;
            st.update(l, r, -k);
        } else {
            int l, r;
            cin >> l >> r;
            cout << st.query(l, r) << endl;
        }
    }
}

prog.cpp:1:1: error: ‘ll’ does not name a type
 ll sq_f(ll x) {
 ^~
prog.cpp:12:9: error: ‘ll’ does not name a type
         ll val, lazy, mn, mx;
         ^~
prog.cpp:13:16: error: expected ‘)’ before ‘_val’
         Node(ll _val = 0, ll _lazy = 0, ll _mn = 0, ll _mx = 0) : val(_val), lazy(_lazy), mn(_mn), mx(_mx) {}
             ~  ^~~~~
                )
prog.cpp:14:24: error: ‘ll’ has not been declared
         Node operator=(ll _val) {
                        ^~
prog.cpp:23:5: error: ‘vector’ does not name a type
     vector<Node> tree;
     ^~~~~~
prog.cpp:24:5: error: ‘vector’ does not name a type
     vector<vector<ll>> pref;
     ^~~~~~
prog.cpp:44:5: error: ‘ll’ does not name a type
     ll range_stage_sum(int s, int l, int r) {
     ^~
prog.cpp:48:41: error: ‘ll’ has not been declared
     void apply(int idx, int lx, int rx, ll delta) {
                                         ^~
prog.cpp:90:22: error: ‘vector’ does not name a type
     void build(const vector<vector<ll>> &vals) {
                      ^~~~~~
prog.cpp:90:28: error: expected ‘,’ or ‘...’ before ‘<’ token
     void build(const vector<vector<ll>> &vals) {
                            ^
prog.cpp:100:31: error: ‘ll’ has not been declared
     void update(int l, int r, ll v, int idx, int lx, int rx) {
                               ^~
prog.cpp:128:31: error: ‘ll’ has not been declared
     void update(int l, int r, ll v) { update(l, r, v, 1, 1, size); }
                               ^~
prog.cpp:130:5: error: ‘ll’ does not name a type
     ll query(int l, int r, int idx, int lx, int rx) {
     ^~
prog.cpp:154:5: error: ‘ll’ does not name a type
     ll query(int l, int r) { return query(l, r, 1, 1, size); }
     ^~
prog.cpp: In member function ‘Lazy_Segment_Tree::Node Lazy_Segment_Tree::Node::operator=(int)’:
prog.cpp:15:13: error: ‘val’ was not declared in this scope
             val = _val;
             ^~~
prog.cpp:15:13: note: suggested alternative: ‘_val’
             val = _val;
             ^~~
             _val
prog.cpp:16:13: error: ‘lazy’ was not declared in this scope
             lazy = 0;
             ^~~~
prog.cpp:17:13: error: ‘mn’ was not declared in this scope
             mn = mx = 0;
             ^~
prog.cpp:17:13: note: suggested alternative: ‘n’
             mn = mx = 0;
             ^~
             n
prog.cpp:17:18: error: ‘mx’ was not declared in this scope
             mn = mx = 0;
                  ^~
prog.cpp: In member function ‘void Lazy_Segment_Tree::init(int)’:
prog.cpp:30:9: error: ‘tree’ was not declared in this scope
         tree.assign(2 * size + 5, Node());
         ^~~~
prog.cpp:31:9: error: ‘pref’ was not declared in this scope
         pref.resize(6);
         ^~~~
prog.cpp: In member function ‘Lazy_Segment_Tree::Node Lazy_Segment_Tree::merge(const Lazy_Segment_Tree::Node&, const Lazy_Segment_Tree::Node&)’:
prog.cpp:37:13: error: ‘struct Lazy_Segment_Tree::Node’ has no member named ‘val’
         res.val = a.val + b.val;
             ^~~
prog.cpp:37:21: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘val’
         res.val = a.val + b.val;
                     ^~~
prog.cpp:37:29: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘val’
         res.val = a.val + b.val;
                             ^~~
prog.cpp:38:13: error: ‘struct Lazy_Segment_Tree::Node’ has no member named ‘lazy’
         res.lazy = 0;
             ^~~~
prog.cpp:39:13: error: ‘struct Lazy_Segment_Tree::Node’ has no member named ‘mn’
         res.mn = min(a.mn, b.mn);
             ^~
prog.cpp:39:24: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘mn’
         res.mn = min(a.mn, b.mn);
                        ^~
prog.cpp:39:30: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘mn’
         res.mn = min(a.mn, b.mn);
                              ^~
prog.cpp:39:18: error: ‘min’ was not declared in this scope
         res.mn = min(a.mn, b.mn);
                  ^~~
prog.cpp:40:13: error: ‘struct Lazy_Segment_Tree::Node’ has no member named ‘mx’
         res.mx = max(a.mx, b.mx);
             ^~
prog.cpp:40:24: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘mx’
         res.mx = max(a.mx, b.mx);
                        ^~
prog.cpp:40:30: error: ‘const struct Lazy_Segment_Tree::Node’ has no member named ‘mx’
         res.mx = max(a.mx, b.mx);
                              ^~
prog.cpp:40:18: error: ‘max’ was not declared in this scope
         res.mx = max(a.mx, b.mx);
                  ^~~
prog.cpp: In member function ‘void Lazy_Segment_Tree::apply(int, int, int, int)’:
prog.cpp:49:9: error: ‘tree’ was not declared in this scope
         tree[idx].mn += delta;
         ^~~~
prog.cpp:63:29: error: ‘range_stage_sum’ was not declared in this scope
             tree[idx].val = range_stage_sum(stage, lx, rx);
                             ^~~~~~~~~~~~~~~
prog.cpp: In member function ‘void Lazy_Segment_Tree::push(int, int, int)’:
prog.cpp:68:13: error: ‘tree’ was not declared in this scope
         if (tree[idx].lazy == 0) return;
             ^~~~
prog.cpp:71:36: error: ‘tree’ was not declared in this scope
             apply(2 * idx, lx, mx, tree[idx].lazy);
                                    ^~~~
prog.cpp:74:9: error: ‘tree’ was not declared in this scope
         tree[idx].lazy = 0;
         ^~~~
prog.cpp: In member function ‘void Lazy_Segment_Tree::build(int, int, int)’:
prog.cpp:78:9: error: ‘tree’ was not declared in this scope
         tree[idx].lazy = 0;
         ^~~~
prog.cpp:81:40: error: ‘range_stage_sum’ was not declared in this scope
             tree[idx].val = (lx <= n ? range_stage_sum(0, lx, rx) : 0);
                                        ^~~~~~~~~~~~~~~
prog.cpp: In member function ‘void Lazy_Segment_Tree::build(int)’:
prog.cpp:91:37: error: ‘pref’ was not declared in this scope
         for (int s = 0; s < 6; s++) pref[s][0] = 0;
                                     ^~~~
prog.cpp:94:17: error: ‘pref’ was not declared in this scope
                 pref[s][i] = pref[s][i - 1] + (i <= n ? vals[s][i] : 0LL);
                 ^~~~
prog.cpp:94:57: error: ‘vals’ was not declared in this scope
                 pref[s][i] = pref[s][i - 1] + (i <= n ? vals[s][i] : 0LL);
                                                         ^~~~
prog.cpp: In member function ‘void Lazy_Segment_Tree::update(int, int, int, int, int, int)’:
prog.cpp:104:17: error: ‘tree’ was not declared in this scope
             if (tree[idx].mn == tree[idx].mx) {
                 ^~~~
prog.cpp:108:17: error: ‘tree’ was not declared in this scope
             if (tree[idx].mn + v >= 5) {
                 ^~~~
prog.cpp:116:17: error: ‘tree’ was not declared in this scope
             if (tree[idx].mn >= 5) tree[idx].val = 1;
                 ^~~~
prog.cpp:117:34: error: ‘range_stage_sum’ was not declared in this scope
             else tree[idx].val = range_stage_sum((int)tree[idx].mn, lx, rx);
                                  ^~~~~~~~~~~~~~~
prog.cpp:125:9: error: ‘tree’ was not declared in this scope
         tree[idx] = merge(tree[2 * idx], tree[2 * idx + 1]);
         ^~~~
prog.cpp: In function ‘void solve()’:
prog.cpp:159:5: error: ‘cin’ was not declared in this scope
     cin >> n;
     ^~~
prog.cpp:160:5: error: ‘vector’ was not declared in this scope
     vector<ll> a(n + 1);
     ^~~~~~
prog.cpp:160:12: error: ‘ll’ was not declared in this scope
     vector<ll> a(n + 1);
            ^~
prog.cpp:160:16: error: ‘a’ was not declared in this scope
     vector<ll> a(n + 1);
                ^
prog.cpp:163:24: error: ‘vals’ was not declared in this scope
     vector<vector<ll>> vals(6);
                        ^~~~
prog.cpp:168:50: error: ‘sq_f’ was not declared in this scope
         for (int s = 1; s < 6; s++) vals[s][i] = sq_f(vals[s - 1][i]);
                                                  ^~~~
prog.cpp:191:13: error: ‘cout’ was not declared in this scope
             cout << st.query(l, r) << endl;
             ^~~~
prog.cpp:191:24: error: ‘struct Lazy_Segment_Tree’ has no member named ‘query’
             cout << st.query(l, r) << endl;
                        ^~~~~
prog.cpp:191:39: error: ‘endl’ was not declared in this scope
             cout << st.query(l, r) << endl;
                                       ^~~~
prog.cpp:191:39: note: suggested alternative: ‘enum’
             cout << st.query(l, r) << endl;
                                       ^~~~
                                       enum

Standard output is empty