結果

問題 No.1099 Range Square Sum
コンテスト
ユーザー Ricky_pon
提出日時 2020-06-27 00:16:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 158 ms / 2,000 ms
コード長 4,480 bytes
コンパイル時間 2,562 ms
コンパイル使用メモリ 206,520 KB
最終ジャッジ日時 2025-01-11 12:22:04
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 30
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:126:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  126 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:128:20: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  128 |     rep(i, n) scanf("%lld", &a[i].se), a[i].fi = a[i].se * a[i].se;
      |               ~~~~~^~~~~~~~~~~~~~~~~~
main.cpp:137:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  137 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
main.cpp:140:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  140 |         scanf("%d%d%d", &t, &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:142:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  142 |             scanf("%lld", &x);
      |             ~~~~~^~~~~~~~~~~~

ソースコード

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