src/test/atc_abc357_f.cpp

• View this file on GitHub
• Last update: 2025-10-08 00:44:44+09:00

Depends on

• src/BucketDecomposition.hpp
• src/modint.hpp
• src/template.hpp

Code

#include "../BucketDecomposition.hpp"
#include "../modint.hpp"

struct Block {
    struct S {
        mint a = 0, b = 0, s = 0;
    };
    struct F {
        mint a = 0, b = 0;
    };
    S sum{};
    F lazy{};
    int n, id;
    vector<S> a;

    Block(int n_, int id_, vector<S> &a_): n(n_), id(id_), a(a_) {
        build();
    }
    S op(S l, S r) { return {l.a + r.a, l.b + r.b, l.s + r.s}; }
    void build() {
        sum = {};
        rep(i, n) {
            a[i].a += lazy.a;
            a[i].b += lazy.b;
            a[i].s = a[i].a * a[i].b;
            sum = op(sum, a[i]);
        }
        lazy = {};
    }

    S all_prod() { return sum; }

    S prod(int l, int r) {
        build();
        S ret = {0, 0, 0};
        for(int i = l; i < r; i++) {
            ret = op(ret, a[i]);
        }
        return ret;
    }

    void all_apply(F f) {
        lazy.a += f.a;
        lazy.b += f.b;
        sum.s += f.a * sum.b + f.b * sum.a + f.a * f.b * n;
        sum.a += f.a * n;
        sum.b += f.b * n;
        return;
    }
    void apply(int l, int r, F f) {
        for(int i = l; i < r; i++) {
            a[i].a += f.a;
            a[i].b += f.b;
            a[i].s += a[i].a * a[i].b;
        }
        build();
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long> A(N), B(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];

    vector<Block::S> init(N);
    rep(i, N) init[i] = Block::S{A[i], B[i], A[i] * B[i]};
    BucketDecomposition<Block> D(init);
    while(Q--) {
        int t, l, r, x;
        cin >> t >> l >> r;
        l--;
        if(t == 1) {
            cin >> x;
            D.apply(l, r, {x, 0});
        }
        else if(t == 2) {
            cin >> x;
            D.apply(l, r, {0, x});
        }
        else {
            cout << D.prod(l, r).s.val() << "\n";
        }
    }
}

#line 1 "src/test/atc_abc357_f.cpp"

#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/BucketDecomposition.hpp"

template<class Block> struct BucketDecomposition {
    using S = Block::S;
    using F = Block::F;

    int N, B;
    vector<Block> blocks;
    BucketDecomposition(vector<S> A, int B_=-1): B(B_) {
        N = A.size();
        if(B==-1) B = sqrt(N) + 1;
        blocks.reserve((N + B - 1) / B);
        rep(i, (N + B - 1) / B) {
            vector<S> a;
            for(int j = i * B; j < min(N, (i + 1) * B); j++) a.push_back(A[j]);
            blocks.push_back(Block(si(a), i, a));
        }
    }
    Block::S prod(int l, int r) {
        int lb = l / B;
        int rb = (r - 1) / B;
        S ret{};
        if(lb == rb)
            ret = blocks[lb].op(ret, blocks[lb].prod(l - B * lb, r - B * lb));
        else {
            for(int i = lb; i <= rb; i++) {
                if(i == lb)
                    ret = blocks[lb].op(ret, blocks[i].prod(l - B * i, B));
                else if(i == rb)
                    ret = blocks[lb].op(ret, blocks[i].prod(0, r - B * i));
                else ret = blocks[lb].op(ret, blocks[i].all_prod());
            }
        }
        return ret;
    }
    void apply(int l, int r, Block::F f) {
        int lb = l / B;
        int rb = (r - 1) / B;
        if(lb == rb) blocks[lb].apply(l - B * lb, r - B * lb, f);
        else {
            for(int i = lb; i <= rb; i++) {
                if(i == lb) blocks[i].apply(l - B * i, B, f);
                else if(i == rb) blocks[i].apply(0, r - B * i, f);
                else blocks[i].all_apply(f);
            }
        }
    }
};
#line 3 "src/modint.hpp"

template<int mod = 998244353> struct modint {
    int x;
    constexpr modint(long x_ = 0): x(x_ % mod) {
        if(x < 0) x += mod;
    }
    constexpr modint operator-() {
        auto res = *this;
        res.x = (x ? mod - x : 0);
        return res;
    }
    constexpr modint& operator+=(modint r) {
        if((x += r.x) >= mod) x -= mod;
        return *this;
    }
    constexpr modint& operator-=(modint r) {
        if((x -= r.x) < 0) x += mod;
        return *this;
    }
    constexpr modint& operator*=(modint r) {
        x = 1LL * x * r.x % mod;
        return *this;
    }
    constexpr modint& operator/=(modint r) { return *this *= r.inv(); }
    constexpr friend modint operator+(modint a, modint b) { return a += b; }
    constexpr friend modint operator-(modint a, modint b) { return a -= b; }
    constexpr friend modint operator*(modint a, modint b) { return a *= b; }
    constexpr friend modint operator/(modint a, modint b) { return a /= b; }
    constexpr modint inv() const { return pow(mod - 2); }
    constexpr modint pow(long b) const {
        assert(0 <= b);
        modint a = *this, c = 1;
        while(b) {
            if(b & 1) c *= a;
            a *= a;
            b >>= 1;
        }
        return c;
    }
    constexpr int val() const { return x; }
    constexpr friend ostream& operator<<(ostream& os, const modint& m) { return os << m.val(); }

    constexpr friend istream& operator>>(istream& is, modint& m) {
        long v;
        is >> v;
        m = modint(v);
        return is;
    }
};
using mint = modint<>;
#line 4 "src/test/atc_abc357_f.cpp"

struct Block {
    struct S {
        mint a = 0, b = 0, s = 0;
    };
    struct F {
        mint a = 0, b = 0;
    };
    S sum{};
    F lazy{};
    int n, id;
    vector<S> a;

    Block(int n_, int id_, vector<S> &a_): n(n_), id(id_), a(a_) {
        build();
    }
    S op(S l, S r) { return {l.a + r.a, l.b + r.b, l.s + r.s}; }
    void build() {
        sum = {};
        rep(i, n) {
            a[i].a += lazy.a;
            a[i].b += lazy.b;
            a[i].s = a[i].a * a[i].b;
            sum = op(sum, a[i]);
        }
        lazy = {};
    }

    S all_prod() { return sum; }

    S prod(int l, int r) {
        build();
        S ret = {0, 0, 0};
        for(int i = l; i < r; i++) {
            ret = op(ret, a[i]);
        }
        return ret;
    }

    void all_apply(F f) {
        lazy.a += f.a;
        lazy.b += f.b;
        sum.s += f.a * sum.b + f.b * sum.a + f.a * f.b * n;
        sum.a += f.a * n;
        sum.b += f.b * n;
        return;
    }
    void apply(int l, int r, F f) {
        for(int i = l; i < r; i++) {
            a[i].a += f.a;
            a[i].b += f.b;
            a[i].s += a[i].a * a[i].b;
        }
        build();
    }
};

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long> A(N), B(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];

    vector<Block::S> init(N);
    rep(i, N) init[i] = Block::S{A[i], B[i], A[i] * B[i]};
    BucketDecomposition<Block> D(init);
    while(Q--) {
        int t, l, r, x;
        cin >> t >> l >> r;
        l--;
        if(t == 1) {
            cin >> x;
            D.apply(l, r, {x, 0});
        }
        else if(t == 2) {
            cin >> x;
            D.apply(l, r, {0, x});
        }
        else {
            cout << D.prod(l, r).s.val() << "\n";
        }
    }
}

Back to top page