結果
問題 | No.1099 Range Square Sum |
ユーザー |
|
提出日時 | 2020-06-26 22:35:58 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 642 ms / 2,000 ms |
コード長 | 2,874 bytes |
コンパイル時間 | 4,618 ms |
コンパイル使用メモリ | 197,768 KB |
最終ジャッジ日時 | 2025-01-11 11:53:21 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#ifdef DEBUG#include <Mylib/Debug/debug.cpp>#else#define dump(...)#endif/*** @title Sqrt decomposition* @docs sqrt_decomposition.md*/struct SqrtDecomposition{const int N;const int BLOCK_SIZE;const int BLOCK_NUM;SqrtDecomposition(int N):N(N), BLOCK_SIZE((int)sqrt(N)), BLOCK_NUM((N + BLOCK_SIZE - 1) / BLOCK_SIZE){}template <typename Func>void init(const Func &f){for(int i = 0; i < BLOCK_NUM; ++i){const int L = i * BLOCK_SIZE;const int R = std::min<int>(N, (i+1) * BLOCK_SIZE);f(i, L, R);}}template <typename FuncBlock, typename FuncRange>void query(int l, int r, const FuncBlock &func_block, const FuncRange &func_range){ // [l, r)for(int i = 0; i < BLOCK_NUM; ++i){const int L = i * BLOCK_SIZE;const int R = std::min<int>(N, (i+1) * BLOCK_SIZE);if(l <= L and R <= r){func_block(i, L, R);}else if((L <= l and l < R) or (L < r and r <= R)){func_range(i, L, R, std::max(l, L), std::min(r, R));}}}};int main(){int N;while(std::cin >> N){std::vector<int64_t> A(N);for(int i = 0; i < N; ++i) std::cin >> A[i];SqrtDecomposition sd(N);std::vector<int64_t> X_sum(sd.BLOCK_NUM);std::vector<int64_t> sq_sum(sd.BLOCK_NUM);std::vector<int64_t> A_sum(sd.BLOCK_NUM);sd.init([&](int i, int L, int R){for(int j = L; j < R; ++j){A_sum[i] += A[j];sq_sum[i] += A[j] * A[j];}});int Q; std::cin >> Q;while(Q--){int type; std::cin >> type;if(type == 1){int64_t l, r, x; std::cin >> l >> r >> x;--l;sd.query(l, r,[&](int i, int L, int R){X_sum[i] += x;sq_sum[i] += x * (2 * A_sum[i] + x * (R - L));A_sum[i] += x * (R - L);},[&](int i, int L, int R, int ll, int rr){for(int j = L; j < R; ++j){A[j] += X_sum[i];}X_sum[i] = 0;for(int j = ll; j < rr; ++j){A_sum[i] += x;sq_sum[i] += x * (2 * A[j] + x);A[j] += x;}});//dump(X_sum, A_sum, sq_sum, A);}else{int64_t l, r; std::cin >> l >> r;--l;int64_t ans = 0;sd.query(l, r,[&](int i, int L, int R){ans += sq_sum[i];},[&](int i, int L, int R, int ll, int rr){for(int j = L; j < R; ++j){A[j] += X_sum[i];}X_sum[i] = 0;for(int j = ll; j < rr; ++j){ans += A[j] * A[j];}});std::cout << ans << "\n";}}}return 0;}