結果
問題 | No.1099 Range Square Sum |
ユーザー |
![]() |
提出日時 | 2020-06-27 00:15:20 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 341 ms / 2,000 ms |
コード長 | 4,370 bytes |
コンパイル時間 | 2,419 ms |
コンパイル使用メモリ | 210,536 KB |
最終ジャッジ日時 | 2025-01-11 12:21:50 |
ジャッジサーバーID (参考情報) |
judge5 / 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); | ~~~~~^~~~~~~~~~~~
ソースコード
#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 secondusing 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<class T, class E> 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> 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);}}