q372. 7. 變異數 - 高中生程式解題系統

Content

　　給定正整數 $N$，以及包含 $N$ 個正整數的序列 $a$。
　　有 $Q$ 筆詢問，對於每筆詢問 $l, r$，請輸出 $a_l\sim a_r$ 的變異數 $\text{Var}_{[l, r]}$。

\begin{aligned}
\mu_{[l, r]} =& \frac{1}{r-l+1}\sum_{i=l}^{r}a_i\\
\text{Var}_{[l, r]} =& \frac{1}{r-l+1}\sum_{i=l}^{r}({a_i}-μ_{[l, r]})^2
\end{aligned}

Input

　　輸入的第一行有兩個正整數 $N, Q$（$1\le N, Q\le 10^6$），代表序列 $a$ 的長度與詢問數量。
　　第二行有 $N$ 個正整數 $a_i$（$1\le a_i\le 4\times 10^6$），為序列 $a$ 的元素內容。
　　接下來有 $Q$ 行，每行有兩個正整數 $l, r$（$1\le l\le r\le N$），代表每筆詢問的區間範圍。

Output

　　對於每筆詢問，請將 $\text{Var}_{[l,r]}$ 四捨五入到整數，並輸出於一行。

Sample Input #1

Sample Output #1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 2.0s , <1K
公開測資點#1 (5%): 2.0s , <1K
公開測資點#2 (5%): 2.0s , <1M
公開測資點#3 (5%): 2.0s , <1M
公開測資點#4 (5%): 2.0s , <1M
公開測資點#5 (5%): 2.0s , <10M
公開測資點#6 (5%): 2.0s , <10M
公開測資點#7 (5%): 2.0s , <50M
公開測資點#8 (5%): 2.0s , <50M
公開測資點#9 (5%): 2.0s , <50M
公開測資點#10 (5%): 2.0s , <50M
公開測資點#11 (5%): 2.0s , <50M
公開測資點#12 (5%): 2.0s , <50M
公開測資點#13 (5%): 2.0s , <50M
公開測資點#14 (5%): 2.0s , <50M
公開測資點#15 (5%): 2.0s , <50M
公開測資點#16 (5%): 2.0s , <50M
公開測資點#17 (5%): 2.0s , <50M
公開測資點#18 (5%): 2.0s , <50M
公開測資點#19 (5%): 2.0s , <50M

Hint ：

本題共有 $4$ 個子題，每個子題有多筆測資。
第一子題：　$N, Q\le 100$，全部解出可得 $25$ 分。
第二子題：　$a_i\le 100$、$Q=1$，全部解出可得 $10$ 分。
第三子題：　$a_i\le 100$，全部解出可得 $50$ 分。
第四子題：　無其它限制，全部解出可得 $15$ 分。

Tags:

前綴和數學

出處:

113學年度新北新莊高中校內資訊學科能力競賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」