結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0