有一天 Mark 遇到了一個數學問題，
「給定一數列 $a_i$，試求 $\sum a_i$ 為奇數還是偶數」
這時他想說這題怎麼那麼水，
但當 Mark 遇到了進階題時，
他卡住了。
「給定 $N$ 個數列，試求這 $N$ 個數列中，有幾個的和為奇數」
Mark 心理想說：「這題是程式題吧？怎麼會出現在數學考卷上？」
但他還是硬著頭皮寫完了。
回家後，
Mark 打開電腦想解幾題程式題，
遇到的第一題題序如下
「給定 $N$ 個數列，這 $N$ 個數列的項數皆為 $p$，且同項的總和定義為 $s_i$ ($s_1 = a_1 + b_1 + ...$)，
請針對 $Q$ 筆詢問做出修改和輸出，
每筆操作的第一行會有一數字 $O$ 代表接下來是要修改還是輸出 ($1$ 為修改、$0$ 為輸出)，
如果需要修改，
則會給定一個長度為 $p$ 的數列 $a_i$，
請把第 $l$ 到 $r$ 的數列針對給定的數列 $a_i$ 做同項相加，
也就是說 $N$ 個數列的 $s_i$ 會被加上 $(r-l+1)\times a_i$。
如果需要輸出，
則請輸出第 $l$ 到 $r$ 的數列的 $s_i$ 是奇數還是偶數。」
這個看似簡單的問題卻考倒 Mark 了，
請你們幫幫他解出這題。
第一行有三個正整數 $N、Q、p$
接下來有 $N$ 行
代表一開始給定的 $N$ 個數列
之後有 $Q$ 行
代表 $Q$ 筆操作
每一行的輸入視給定的 $O$ 決定
如果 $O=1$ 則為 $O、l、r、a_1 ... a_p$
如果 $O=0$ 則為 $O、l、r$
針對每筆 $O=0$ 輸出第 $l$ 到 $r$ 的 $s_i$ 有幾個為奇數
3 4 3 1 2 3 2 1 4 5 1 1 0 1 3 1 2 3 2 3 4 0 1 2 0 1 3
0 2 0
$1\leq N, Q\leq 10^5$
$1\leq p\leq 30$
$1\leq 所有數列各項的值\leq 10^9$
$O\in \{0, 1\}$
$1\leq l \leq r\leq N$
$15\%$ 的測資: $N, Q\leq 10^3$
$30\%$ 的測資: $N, Q\leq 10^4$
$100\%$ 的測資: 無其他條件限制
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||