結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2020-08-13 18:48:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 388 ms / 2,000 ms |
コード長 | 2,895 bytes |
コンパイル時間 | 2,213 ms |
コンパイル使用メモリ | 198,004 KB |
最終ジャッジ日時 | 2025-01-12 21:55:07 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
//#define _GLIBCXX_DEBUG#include <bits/stdc++.h>#define rep(i, n) for(int i=0; i<n; ++i)#define all(v) v.begin(), v.end()#define rall(v) v.rbegin(), v.rend()using namespace std;using ll = int64_t;using ld = long double;using P = pair<int, int>;using vs = vector<string>;using vi = vector<int>;using vvi = vector<vi>;template<class T> using PQ = priority_queue<T>;template<class T> using PQG = priority_queue<T, vector<T>, greater<T> >;const int INF = 100010001;const ll LINF = (ll)INF*INF*10;template<typename T1, typename T2>inline bool chmax(T1 &a, T2 b) {return a < b && (a = b, true);}template<typename T1, typename T2>inline bool chmin(T1 &a, T2 b) {return a > b && (a = b, true);}template<typename T1, typename T2>istream &operator>>(istream &is, pair<T1, T2> &p) { return is >> p.first >> p.second;}template<typename T1, typename T2>ostream &operator<<(ostream &os, const pair<T1, T2> &p) { return os << p.first << ' ' << p.second;}const size_t N = 2e5+10;//headint n, m, q;ll a[N];vector<ll> b, c;vi ev;void eval(int k) {if(ev[k] == 0) return;for(int i = k*m; i < min(n, (k+1)*m); i++) {a[i] += ev[k];}ev[k] = 0;}void add(int l, int r, ll x) {eval(l/m);eval(r/m);if(l/m == r/m) {b[l/m] += x*(r-l);for(int i = l; i < r; i++) {c[l/m] += x*x + 2*x*a[i];a[i] += x;}return;}if(l%m) b[l/m] += x*(m-(l%m));for(int &i = l; i%m; i++) {c[l/m] += x*x + 2*x*a[i];a[i] += x;}b[r/m] += x*(r%m);for(int &i = r; i%m;) {i--;c[r/m] += x*x + 2*x*a[i];a[i] += x;}for(int i = l/m; i < r/m; i++) {ev[i] += x;c[i] += x*x*m + 2*b[i]*x;b[i] += x*m;}}ll query(int l, int r) {ll res = 0;eval(l/m);eval(r/m);if(l/m == r/m) {for(int i = l; i < r; i++) {res += a[i]*a[i];}return res;}//cout << l << ' ' << r << endl;for(int &i = l; i%m; i++) {//cout << i << endl;res += a[i]*a[i];}for(int &i = r; i%m;) {i--;//cout << i << endl;res += a[i]*a[i];}for(int i = l/m; i < r/m; i++) {//cout << i << endl;res += c[i];}return res;}int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n;m = sqrt(n);b.resize((n+m-1)/m);c.resize((n+m-1)/m);ev.resize((n+m-1)/m);rep(i, n) cin >> a[i];rep(i, n) {b[i/m] += a[i];c[i/m] += a[i]*a[i];}cin >> q;while(q--) {int t;cin >> t;if(t == 1) {int l, r;ll x;cin >> l >> r >> x;add(l-1, r, x);/*rep(i, n+m-1) {eval(i);}rep(i, n+1) rep(j, i) {ll res = 0;for(int k = j; k < i; k++) res += a[k]*a[k];cout << j << ' ' << i << ' ' << res << ' ' << query(j, i) << '\n';}*/}else {int l, r;cin >> l >> r;cout << query(l-1, r) << '\n';}}}