結果

問題 No.1099 Range Square Sum
ユーザー Ricky_ponRicky_pon
提出日時 2020-06-27 00:16:50
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 156 ms / 2,000 ms
コード長 4,480 bytes
コンパイル時間 2,203 ms
コンパイル使用メモリ 213,932 KB
実行使用メモリ 25,984 KB
最終ジャッジ日時 2024-07-05 01:38:00
合計ジャッジ時間 5,313 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 3 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 3 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 3 ms
5,376 KB
testcase_19 AC 3 ms
5,376 KB
testcase_20 AC 3 ms
5,376 KB
testcase_21 AC 155 ms
25,960 KB
testcase_22 AC 152 ms
25,952 KB
testcase_23 AC 154 ms
25,984 KB
testcase_24 AC 156 ms
25,964 KB
testcase_25 AC 155 ms
25,936 KB
testcase_26 AC 120 ms
25,948 KB
testcase_27 AC 118 ms
25,960 KB
testcase_28 AC 117 ms
25,956 KB
testcase_29 AC 119 ms
25,904 KB
testcase_30 AC 116 ms
25,952 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

template<typename T, typename E, typename F, typename G, typename H, typename P> struct LazySegTree{
    /*using F = function<T(T, T)>;
    using G = function<T(T, E)>;
    using H = function<E(E, E)>;
    using P = function<E(E, int)>;*/
    int sz = 1, seq_sz; F f; G g; H h; T et; E ee; P p;
    int cur = 0;
    vector<T> node;
    vector<E> lazy;
    vector<int> idx, len;

    LazySegTree(int sz_, T et_, E ee_, F f_, G g_, H h_, P p_=[](E a, int b){return a;}):
    seq_sz(sz_), et(et_), ee(ee_), f(f_), g(g_), h(h_), p(p_){
        while(sz < sz_) sz <<= 1;
        node.resize(sz<<1, et);
        lazy.resize(sz<<1, ee);
        idx.resize(sz, -1);
        len.resize(sz<<1, 0);
        For(i, sz, sz<<1) len[i] = 1;
        rFor(i, sz, 1) len[i] = len[i<<1] + len[(i<<1)+1];
    }

    void build(vector<T> &a){
        rep(i, a.size()) node[i+sz] = a[i];
        rFor(i, sz, 1) node[i] = f(node[i<<1], node[(i<<1)+1]);
    }

    void build(T x){
        rep(i, seq_sz) node[i+sz] = x;
        rFor(i, sz, 1) node[i] = f(node[i<<1], node[(i<<1)+1]);
    }

    inline void push(int i){
        if(lazy[i] == ee) return;
        if(i < sz) {
            lazy[i << 1] = h(lazy[i << 1], lazy[i]);
            node[i << 1] = g(node[i << 1], p(lazy[i], len[i << 1]));
            lazy[(i << 1) + 1] = h(lazy[(i << 1) + 1], lazy[i]);
            node[(i << 1) + 1] = g(node[(i << 1) + 1], p(lazy[i], len[(i << 1) + 1]));
        }
        lazy[i] = ee;
    }

    inline void prop(int l, int r){
        cur = 0;
        if(l == sz && r == sz<<1) return;
        l = (l / (l & -l)) >> 1;
        r = (r / (r & -r)) >> 1;
        while(l > 1 || r > 1){
            if(l >= r){
                idx[cur++] = l;
                l >>= 1;
            }
            else{
                idx[cur++] = r;
                r >>= 1;
            }
        }
        idx[cur++] = 1;

        rrep(k, cur) push(idx[k]);
    }

    void update(int l, int r, E x){
        l += sz; r += sz;
        prop(l, r);
        for(; l<r; l>>=1, r>>=1){
            if(l & 1){
                lazy[l] = h(lazy[l], x);
                node[l] = g(node[l], p(x, len[l]));
                ++l;
            }
            if(r & 1){
                --r;
                lazy[r] = h(lazy[r], x);
                node[r] = g(node[r], p(x, len[r]));
            }
        }
        rep(k, cur){
            int i = idx[k];
            if(i < sz) node[i] = f(node[i<<1], node[(i<<1)+1]);
        }
    }

    T query(int l, int r){
        l += sz; r += sz;
        prop(l, r);
        T vl = et, vr = et;
        for(; l<r; l>>=1, r>>=1){
            if(l & 1) vl = f(vl, node[l++]);
            if(r & 1) vr = f(node[--r], vr);
        }
        return f(vl, vr);
    }
};

int main(){
    int n;
    scanf("%d", &n);
    vector<pll> a(n);
    rep(i, n) scanf("%lld", &a[i].se), a[i].fi = a[i].se * a[i].se;
    auto f = [](pll p, pll q){return make_pair(p.fi+q.fi, p.se+q.se);};
    auto g = [](pll p, pll q){return make_pair(p.fi + 2*p.se*q.fi + q.se*q.fi*q.fi, p.se + q.se*q.fi);};
    auto h = [](pll p, pll q){return make_pair(p.fi+q.fi, 0);};
    auto p = [](pll p, lint len){return make_pair(p.fi, len);};
    LazySegTree<pll, pll, decltype(f), decltype(g), decltype(h), decltype(p)> lst(n, {0, 0}, {0, 0}, f, g, h, p);
    lst.build(a);

    int q;
    scanf("%d", &q);
    rep(_, q){
        int t, l, r; lint x;
        scanf("%d%d%d", &t, &l, &r);
        if(t == 1){
            scanf("%lld", &x);
            lst.update(l-1, r, {x, 0});
        }
        else printf("%lld\n", lst.query(l-1, r).fi);
    }
}
0