內容
給定正整數 $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}
輸入說明
輸入的第一行有兩個正整數 $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$），代表每筆詢問的區間範圍。
輸出說明
對於每筆詢問，請將 $\text{Var}_{[l,r]}$ 四捨五入到整數，並輸出於一行。
範例輸入
#1
5 4 3 2 4 1 5 2 2 1 3 3 4 1 5
範例輸出
#1
0 1 2 2
測資資訊：
記憶體限制：
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
公開 測資點#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
提示 ：
本題共有 $4$ 個子題，每個子題有多筆測資。
第一子題： $N, Q\le 100$，全部解出可得 $25$ 分。
第二子題： $a_i\le 100$、$Q=1$，全部解出可得 $10$ 分。
第三子題： $a_i\le 100$，全部解出可得 $50$ 分。
第四子題： 無其它限制，全部解出可得 $15$ 分。
出處:
113學年度新北新莊高中校內資訊學科能力競賽
[管理者：
liaoweichen1
...
(M_SQRT)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||