結果

問題 No.1099 Range Square Sum
ユーザー Haar
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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