結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2020-08-13 17:59:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,553 bytes |
コンパイル時間 | 2,942 ms |
コンパイル使用メモリ | 197,896 KB |
最終ジャッジ日時 | 2025-01-12 21:54:52 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 7 WA * 23 |
ソースコード
//#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;}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;}}void 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];}cout << res << '\n';return;}for(int &i = l; i%m; i++) {res += a[i]*a[i];}for(int &i = r; i%m;) {i--;res += a[i]*a[i];}for(int i = l/m; i < r/m; i++) {res += c[i];}cout << res << '\n';return;}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, x;cin >> l >> r >> x;add(l-1, r, x);}else {int l, r;cin >> l >> r;query(l-1, r);}}}