結果

問題 No.1099 Range Square Sum
ユーザー Ricky_pon
提出日時 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);
      |             ~~~~~^~~~~~~~~~~~

ソースコード

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<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);
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0