NTUCPC Speed Run! #1 NTUCPC Speed Run! #1 將於 2024-10-05 14:00 ~ 17:00 舉行
APCSCamp 海量題目公開！ 連結
程式解題社網站 程式解題社網站上線了！
APCSCamp 海量題目公開！ 連結
程式解題社網站 程式解題社網站上線了！
198 . 捯捯捯
TopCoder
Tags
Description
給定一個長度為 $n$ 的陣列 $a$，接下來有 $q$ 筆操作。
第一種操作：給定 $l, r, x, y$，$\forall l \leq i \leq r$，$a_i = a_i + x + (i - l) \times y$
第二種操作：給定 $l, r$，問區間 $a[l \ldots r]$ 最少可以被分割為幾個等差數列。
注意：每一個被分割出來的等差數列都是 $a$ 的一個連續區間。
此題為多筆測資。
Input Format
第一行有一個整數 $t$，代表你需要處理的測資筆數。
對於每一筆測資，第一行有一個整數 $n$。
第二行有 $n$ 個整數 $a_1, a_2, ..., a_n$，代表陣列的初始值。
第三行有一個整數 $q$。
第四行開始的 $q$ 行的每一行是一個操作，形式如下：
- 第一種操作，操作的形式為 $1\ l\ r\ x\ y$
- 第二種操作，操作的形式為 $2\ l\ r$
資料滿足：
- $1 \leq \sum n, \sum q \leq 10^ 5$
- $|a_i|, |x|, |y| \leq 10^ 6$
- $1 \leq l \leq r \leq n$
Output Format
對於每一筆第二種詢問，輸出解並換行。
Sample Input 1
1
6
82 -7 19 4 -311 1019
10
2 1 3
2 3 6
1 1 2 115 0
2 1 3
1 3 5 7 46
1 4 6 -3 -2
1 4 6 3 18
1 1 5 -10 8
1 2 5 0 0
2 1 6
6
82 -7 19 4 -311 1019
10
2 1 3
2 3 6
1 1 2 115 0
2 1 3
1 3 5 7 46
1 4 6 -3 -2
1 4 6 3 18
1 1 5 -10 8
1 2 5 0 0
2 1 6
Sample Output 1
2
2
1
3
2
1
3
Hints
Problem Source
IOICamp 2022 Day5 pM
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~41 | 無額外限制 | 100 |