968 . 旋轉相除法
TopCoder
Tags
Description
抹茶貓想在樹上睡覺，於是她灑下了幾顆線段樹的種子，希望他們能夠快快長大。
給你長度 $n$ 的正整數序列 $\langle a \rangle$，請支援 $q$ 筆操作：
- $\texttt{1} \;\; \ell \;\; r$：對 $i \in [\ell, r-1]$，同時讓 $a_i \gets \lceil a_i / a_{i+1} \rceil$，並讓 $a_r \gets \lceil a_r / a_\ell \rceil$。
- $\texttt{2} \;\; \ell \;\; r \;\; x$：對 $i \in [\ell, r]$，讓 $a_i \gets a_i + x$。
- $\texttt{3} \;\; \ell \;\; r \;\; x$：對 $i \in [\ell, r]$，讓 $a_i \gets x$。
- $\texttt{4} \;\; \ell \;\; r$：輸出 $\sum_{i=\ell}^ {r} a_i$。
Input Format
- line $1$: $\;\; n \;\; q$
- line $2$: $\;\; a_1 \;\; a_2 \;\; \ldots \;\; a_n$
- line $2+i$ ($1 \le i \le q$): $\;\; \textsf{Query}_i$
- $\textsf{Query}_i$ 是以下其中一種：
- $\texttt{1} \;\; \ell \;\; r$
- $\texttt{2} \;\; \ell \;\; r \;\; x$
- $\texttt{3} \;\; \ell \;\; r \;\; x$
- $\texttt{4} \;\; \ell \;\; r$
- $\textsf{Query}_i$ 是以下其中一種：
資料範圍：
- $1 \le n \le 100\,000$。
- $1 \le q \le 100\,000$。
- $1 \le a_i \le 10^ 8$（$1 \le i \le n$）。
- 對每個操作，$op \in \lbrace\texttt{1}, \texttt{2}, \texttt{3}, \texttt{4}\rbrace$。
- 對每個操作，$1 \le \ell \le r \le n$。
- 對每個 $op \in \lbrace\texttt{2}, \texttt{3}\rbrace$ 的操作，$1 \le x \le 10^ 8$。
- 輸入的數字均為整數。
Output Format
- line $j$: $\;\; \text{ans}_j$
- $\text{ans}_j$ 是第 $j$ 個類型 $4$ 查詢的答案。
Sample Input 1
7 7 3 1 4 5 9 2 6 4 1 7 3 6 7 3 4 1 7 2 2 3 7 4 1 7 1 1 7 4 1 7
Sample Output 1
30 28 42 11
Hints
範例一
該輸入滿足子任務 1, 6 的限制。
每次操作後的序列如下：
| 操作＼序列 | $\langle a \rangle$ |
| $\texttt{4 1 7}$ | $\texttt{[3 1 4 5 9 2 6]}$ |
| $\texttt{3 6 7 3}$ | $\texttt{ 3 1 4 5 9 [3 3]}$ |
| $\texttt{4 1 7}$ | $\texttt{[3 1 4 5 9 3 3]}$ |
| $\texttt{2 2 3 7}$ | $\texttt{ 3 [8 11] 5 9 3 3 }$ |
| $\texttt{4 1 7}$ | $\texttt{[3 8 11 5 9 3 3]}$ |
| $\texttt{1 1 7}$ | $\texttt{[1 1 3 1 3 1 1]}$ |
| $\texttt{4 1 7}$ | $\texttt{[1 1 3 1 3 1 1]}$ |
特別地，第六次操作 $\texttt{1 1 7}$ 說明如下：
| 說明 | $a_1$ | $a_2$ | $a_3$ | $a_4$ | $a_5$ | $a_6$ | $a_7$ |
| 操作前 | $3$ | $8$ | $11$ | $5$ | $9$ | $3$ | $3$ |
| 分母 | $8$ | $11$ | $5$ | $9$ | $3$ | $3$ | $3$ |
| 操作後 | $1$ | $1$ | $3$ | $1$ | $3$ | $1$ | $1$ |
Problem Source
YTP 2025 高中組程式挑戰營 p18
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 46 | 範例測試資料。 | 0 |
| 2 | 14~19, 26~27, 35~37, 44~46, 48, 51, 53, 55 | $n \le 1000$、$q \le 1000$。 | 1 |
| 3 | 38~45, 54~55 | $op \in \lbrace\texttt{1}, \texttt{4}\rbrace$。 | 5 |
| 4 | 0~5, 38~45, 54~55 | $op \in \lbrace\texttt{1}, \texttt{3}, \texttt{4}\rbrace$、對所有 $op = 3$ 的操作皆滿足 $\ell = r$。 | 3 |
| 5 | 20~27, 38~45, 49~51, 54~55 | $op \in \lbrace\texttt{1}, \texttt{2}, \texttt{4}\rbrace$。 | 6 |
| 6 | 0~5, 28~45, 52~55 | $op \in \lbrace\texttt{1}, \texttt{3}, \texttt{4}\rbrace$。 | 6 |
| 7 | 0~55 | 無額外限制。 | 4 |