結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー knshnb
提出日時 2020-02-28 22:06:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 459 ms / 2,000 ms
コード長 5,301 bytes
コンパイル時間 2,224 ms
コンパイル使用メモリ 202,920 KB
最終ジャッジ日時 2025-01-09 02:46:31
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>  // clang-format off
using namespace std;
using Int = long long;
#define REP2(i, n) for (Int i = 0, max_i = (n); i < max_i; i++)
#define REP3(i, a, b) for (Int i = (a), max_i = (b); i < max_i; i++)
#define OVERLOAD2(_1, _2, _3, name, ...) name
#define REP(...) OVERLOAD2(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
struct SetupIO { SetupIO() { cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(13); } } setup_io;
#ifndef _MY_DEBUG
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Fri Feb 28 21:36:59 JST 2020
 **/

// T0: 元の配列のモノイド
// T1: T0に対する作用素モノイド
template <class T0, class T1, class F0, class F1, class G, class P> class LazySegmentTree {
    // k番目のノードにのlazyを伝搬
    void eval(int k, int len) {
        // 定数倍高速化
        // if (lazy[k] == u1) return;
        // len個分のlazy[k]を評価
        node[k] = g(node[k], p(lazy[k], len));
        if (k < N - 1) {
            // 最下段でなければ下のlazyに伝搬
            lazy[2 * k + 1] = f1(lazy[2 * k + 1], lazy[k]);
            lazy[2 * k + 2] = f1(lazy[2 * k + 2], lazy[k]);
        }
        lazy[k] = u1;
    }
    // k番目のノード[l, r)について、[a, b)の範囲内にxを作用
    void update(int a, int b, T1 x, int k, int l, int r) {
        eval(k, r - l);
        if (b <= l || r <= a) return;
        if (a <= l && r <= b) {
            lazy[k] = f1(lazy[k], x);
            eval(k, r - l);
        } else {
            update(a, b, x, 2 * k + 1, l, (l + r) / 2);
            update(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = f0(node[2 * k + 1], node[2 * k + 2]);
        }
    }
    // k番目のノード[l, r)について、[a, b)のクエリを求める
    T0 query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return u0;
        eval(k, r - l);
        if (a <= l && r <= b) return node[k];
        T0 vl = query(a, b, 2 * k + 1, l, (l + r) / 2);
        T0 vr = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return f0(vl, vr);
    }

public:
    int sz;  // 元の配列のサイズ
    int N;
    vector<T0> node;
    vector<T1> lazy;
    // T0上の演算、単位元
    const F0 f0;
    const T0 u0;
    // T1上の演算、単位元
    const F1 f1;
    const T1 u1;
    // T0に対するT1の作用
    const G g;
    // 多数のt1(T1)に対するf1の合成
    const P p;

    LazySegmentTree(F0 f0, T0 u0, F1 f1, T1 u1, G g, P p) : f0(f0), u0(u0), f1(f1), u1(u1), g(g), p(p) {}
    void set_by_vector(const vector<T0>& a) {
        sz = a.size();
        for (N = 1; N < sz; N *= 2)
            ;
        node.resize(2 * N - 1, u0);
        lazy.resize(2 * N - 1, u1);
        for (int i = 0; i < sz; i++) node[N - 1 + i] = a[i];
        for (int i = N - 2; i >= 0; i--) node[i] = f0(node[2 * i + 1], node[2 * i + 2]);
    }
    void set_by_unit(int n) {
        sz = n;
        for (N = 1; N < sz; N *= 2)
            ;
        node.resize(2 * N - 1, u0);
        lazy.resize(2 * N - 1, u1);
    }
    // [a, b)にxを作用
    void update(int a, int b, T1 x) {
        assert(0 <= a && a < b && b <= sz);
        update(a, b, x, 0, 0, N);
    }
    void update(int a, T1 x) { update(a, a + 1, x); }
    // [a, b)
    T0 query(int a, int b) { return query(a, b, 0, 0, N); }
    T0 query(int a) { return query(a, a + 1); }
    friend string to_string(LazySegmentTree<T0, T1, F0, F1, G, P>& seg) {
        for (int i = 0; i < seg.sz; i++) seg.query(i);
        return to_string(vector<T0>(seg.node.begin() + (seg.N - 1), seg.node.begin() + (seg.N - 1 + seg.sz)));
    }
};
template <class T0, class T1, class F0, class F1, class G, class P>
auto make_lazy_segment_tree(F0 f0, T0 u0, F1 f1, T1 u1, G g, P p) {
    return LazySegmentTree<T0, T1, F0, F1, G, P>(f0, u0, f1, u1, g, p);
}
// Max && Add
// constexpr Int INF = 1e18;
// auto seg = make_lazy_segment_tree<Int, Int>(
//     [](Int x, Int y) { return max(x, y); }, -INF, [](Int x, Int y) { return x + y; }, 0,
//     [](Int x, Int y) { return x == -INF ? x : x + y; }, [](Int x, int len) { return x; });

signed main() {
    Int n, Q;
    cin >> n >> Q;
    struct Node {
        Int num, cur, sum;
        bool operator==(Node& rhs) {
            return num == rhs.num && cur == rhs.cur && sum == rhs.cur;
        }
    };
    vector<Node> a(n);
    REP(i, n) {
        Int x;
        cin >> x;
        a[i] = {0, x, 0};
    }
    auto seg = make_lazy_segment_tree<Node, Node>(
        [](Node x, Node y) { return Node{x.num + y.num, x.cur + y.cur, x.sum + y.sum + y.num * x.cur}; }, {0, 0, 0},
        [](Node x, Node y) { return Node{x.num + y.num, x.cur + y.cur, x.sum + y.sum + y.num * x.cur}; }, {0, 0, 0},
        [](Node x, Node y) { return Node{x.num + y.num, x.cur + y.cur, x.sum + y.sum + y.num * x.cur}; },
        [](Node x, int y) { return x; }
    );
    seg.set_by_vector(a);
    REP(q, Q) {
        char c;
        cin >> c;
        Int x, y;
        cin >> x >> y;
        x--;
        if (c == 'A') {
            seg.update(x, {0, y, 0});
        } else {
            seg.update(x, y, {1, 0, 0});
        }
    }
    REP(i, n) {
        Node no = seg.query(i);
        cout << no.sum << " ";
    }
    cout << endl;
}
0