結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー firiexp
提出日時 2020-02-28 21:45:24
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 347 ms / 2,000 ms
コード長 3,320 bytes
コンパイル時間 1,199 ms
コンパイル使用メモリ 106,944 KB
実行使用メモリ 20,608 KB
最終ジャッジ日時 2024-11-15 19:15:35
合計ジャッジ時間 6,450 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <limits>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <class M>
struct LazySegmentTree{
    using T = typename M::T;
    using L = typename M::L;
    int sz, height{};
    vector<T> seg; vector<L> lazy;
    explicit LazySegmentTree(int n) {
        sz = 1; while(sz < n) sz <<= 1, height++;
        seg.assign(2*sz, M::e());
        lazy.assign(2*sz, M::l());
    }

    void set(int k, const T &x){
        seg[k + sz] = x;
    }

    void build(){
        for (int i = sz-1; i > 0; --i) seg[i] = M::f(seg[i<<1], seg[(i<<1)|1]);
    }

    T reflect(int k){ return lazy[k] == M::l() ? seg[k] : M::g(seg[k], lazy[k]); }

    void eval(int k){
        if(lazy[k] == M::l()) return;
        lazy[(k<<1)|0] = M::h(lazy[(k<<1)|0], lazy[k]);
        lazy[(k<<1)|1] = M::h(lazy[(k<<1)|1], lazy[k]);
        seg[k] = reflect(k);
        lazy[k] = M::l();
    }
    void thrust(int k){ for (int i = height; i; --i) eval(k>>i); }
    void recalc(int k) { while(k >>= 1) seg[k] = M::f(reflect((k<<1)|0), reflect((k<<1)|1));}
    void update(int a, int b, const L &x){
        thrust(a += sz); thrust(b += sz-1);
        for (int l = a, r = b+1;l < r; l >>=1, r >>= 1) {
            if(l&1) lazy[l] = M::h(lazy[l], x), l++;
            if(r&1) --r, lazy[r] = M::h(lazy[r], x);
        }
        recalc(a);
        recalc(b);
    }

    T query(int a, int b){ // [l, r)
        thrust(a += sz);
        thrust(b += sz-1);
        T ll = M::e(), rr = M::e();
        for(int l = a, r = b+1; l < r; l >>=1, r>>=1) {
            if (l & 1) ll = M::f(ll, reflect(l++));
            if (r & 1) rr = M::f(reflect(--r), rr);
        }
        return M::f(ll, rr);
    }
};

struct Monoid{
    using T = pair<ll, ll>;
    using L = ll;
    static T f(T a, T b) { return {a.first+b.first, a.second+b.second}; }
    static T g(T a, L b) {
        return {a.first+a.second*b, a.second};
    }
    static L h(L a, L b) {
        return a+b;
    }
    static T e() { return {0, 0}; }
    static L l() { return 0; }
};

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    vector<int> imos(n+1);
    vector<ll> ans(n);
    vector<char> cs(q);
    vector<int> xs(q), ys(q);
    LazySegmentTree<Monoid> seg(n);
    for (int i = 0; i < n; ++i) {
        seg.set(i, {0, 1});
    }
    seg.build();
    for (int i = 0; i < q; ++i) {
        char c; int x, y;
        scanf(" %c %d %d", &c, &x, &y);
        cs[i] = c; xs[i] = x; ys[i] = y;
        if(c == 'B'){
            imos[x-1]++; imos[y]--;
            seg.update(x-1, y, 1);
        }
    }
    for (int i = 0; i < q; ++i) {
        if(cs[i] == 'A'){
            ans[xs[i]-1] += ys[i]*seg.query(xs[i]-1, xs[i]).first;
        } else seg.update(xs[i]-1, ys[i], -1);
    }
    for (int i = 0; i < n; ++i) {
        imos[i+1] += imos[i];
    }

    for (int i = 0; i < n; ++i) {
        if(i) printf(" ");
        printf("%lld", ans[i]+(ll)v[i]*imos[i]);
    }

    return 0;
}
0