No.1099 Range Square Sum
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
SSRS
QCFium