問題一覧 > 通常問題

No.1099 Range Square Sum

レベル : / AI推定難易度 : 1500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 137
作問者 : SSRS / テスター : QCFium
お気に入りにしたユーザー ProblemId : 4374 / 自分の提出
問題文最終更新日: 2020-06-25 22:20:36
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 254 (順位表) の他の問題:

Problem Statement

You are given a sequence $A_1,A_2,\cdots,A_N$ with $N$ elements.
A total of $Q$ queries of the following $2$ types are given, so process them.

  • Query 1:
     $1 \ l \ r \ x$ 
    Add $x$ to all of $A_l,A_{l+1},\cdots,A_r$.

  • Query 2:
     $2 \ l \ r$ 
    Output the value of $\displaystyle \sum_{i=l}^{r}A_i^2 = A_l^2+A_{l+1}^2+\cdots+A_r^2$.

Input

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

The input satisfies the following constraints.

  • All input values are integers.
  • $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$
  • Query 1
    • $1 \leq l \leq r \leq N$
    • $-10^6 \leq x \leq 10^6$
  • Query 2
    • $1 \leq l \leq r \leq N$
  • There is at least one Query 2.
  • At no point in time do $A_1,A_2,\cdots,A_N$ contain a value whose absolute value is greater than $10^6$.

Output

For each Query 2, output the value of $\displaystyle \sum_{i=l}^{r}A_i^2 = A_l^2+A_{l+1}^2+\cdots+A_{r}^2$.

Sample

Sample 1
Input
5
1 2 -3 0 1
5
2 1 3
1 2 4 1
1 4 5 -2
2 3 5
2 1 4
Output
14
6
15

In the 1st query, output $1^2+2^2+(-3)^2=14$.
In the 2nd query, $1$ is added to the elements $2,-3,0$ of the sequence, so the sequence becomes $1,3,-2,1,1$.
In the 3rd query, $-2$ is added to the elements $1,1$ of the sequence, so the sequence becomes $1,3,-2,-1,-1$.
In the 4th query, output $(-2)^2+(-1)^2+(-1)^2=6$.
In the 5th query, output $1^2+3^2+(-2)^2+(-1)^2=15$.

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