問題一覧 > 通常問題

No.1099 Range Square Sum

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 72
作問者 : SSRSSSRS / テスター : QCFiumQCFium
7 ProblemId : 4374 / 出題時の順位表
問題文最終更新日: 2020-06-25 22:20:36

問題文

要素数$N$の数列$A_1,A_2,\cdots,A_N$が与えられます。
以下の$2$種類のクエリが合計$Q$個与えられるので、処理してください。

  • クエリ1:
     $1 \ l \ r \ x$ 
    $A_l,A_{l+1},\cdots,A_r$すべてに$x$を加える

  • クエリ2:
     $2 \ l \ r$ 
    $\displaystyle \sum_{i=l}^{r}A_i^2 = A_l^2+A_{l+1}^2+\cdots+A_r^2$の値を出力する

入力

$N$
$A_1 \ A_2 \ \cdots \ A_N$
$Q$
$query_1$
$query_2$
$\vdots$
$query_Q$

入力は以下の制約を満たします。

  • 入力はすべて整数
  • $1 \leq N \leq 2\times10^5$
  • $-10^6 \leq A_i \leq 10^6 (1 \leq i \leq N)$
  • $1 \leq Q \leq 10^5$
  • クエリ1
    • $1 \leq l \leq r \leq N$
    • $-10^6 \leq x \leq 10^6$
  • クエリ2
    • $1 \leq l \leq r \leq N$
  • クエリ2は1つ以上存在する
  • どの時点においても、$A_1,A_2,\cdots,A_N$に絶対値が$10^6$より大きい値が含まれることはない

出力

各クエリ2に対して、$\displaystyle \sum_{i=l}^{r}A_i^2 = A_l^2+A_{l+1}^2+\cdots+A_{r}^2$の値を出力してください。

サンプル

サンプル1
入力
5
1 2 -3 0 1
5
2 1 3
1 2 4 1
1 4 5 -2
2 3 5
2 1 4
出力
14
6
15

1回目のクエリでは、$1^2+2^2+(-3)^2=14$を出力します。
2回目のクエリでは、数列の要素$2,-3,0$に$1$が加えられるので、数列は$1,3,-2,1,1$になります。
3回目のクエリでは、数列の要素$1,1$に$-2$が加えられるので、数列は$1,3,-2,-1,-1$になります。
4回目のクエリでは、$(-2)^2+(-1)^2+(-1)^2=6$を出力します。
5回目のクエリでは、$1^2+3^2+(-2)^2+(-1)^2=15$を出力します。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。