結果

問題 No.1099 Range Square Sum
ユーザー HaarHaar
提出日時 2020-06-26 22:35:58
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 459 ms / 2,000 ms
コード長 2,874 bytes
コンパイル時間 2,254 ms
コンパイル使用メモリ 204,012 KB
実行使用メモリ 4,724 KB
最終ジャッジ日時 2023-09-18 06:03:50
合計ジャッジ時間 8,331 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 3 ms
4,376 KB
testcase_12 AC 4 ms
4,376 KB
testcase_13 AC 4 ms
4,376 KB
testcase_14 AC 3 ms
4,376 KB
testcase_15 AC 3 ms
4,376 KB
testcase_16 AC 4 ms
4,380 KB
testcase_17 AC 3 ms
4,376 KB
testcase_18 AC 3 ms
4,376 KB
testcase_19 AC 4 ms
4,376 KB
testcase_20 AC 4 ms
4,380 KB
testcase_21 AC 452 ms
4,660 KB
testcase_22 AC 457 ms
4,724 KB
testcase_23 AC 459 ms
4,572 KB
testcase_24 AC 459 ms
4,584 KB
testcase_25 AC 459 ms
4,716 KB
testcase_26 AC 424 ms
4,544 KB
testcase_27 AC 423 ms
4,536 KB
testcase_28 AC 424 ms
4,648 KB
testcase_29 AC 421 ms
4,720 KB
testcase_30 AC 428 ms
4,588 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0