902 . 巴已己放球問題

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

brAnChes1029

User's AC Ratio

96.4% (27/28)

Submission's AC Ratio

47.6% (30/63)

Tags

ioicamp ioicamp-2025

Description

巴已己有 $n$ 個箱子，這些箱子由左到右排成一排，編號依序為 $1$ 到 $n$。一開始每個箱子都是空的，接下來巴已己會進行 $q$ 次操作，操作有四種：

  1. 1 x y，代表巴已己會在第 $x$ 個箱子裡面多放 $y$ 顆球。
  2. 2 x，代表巴已己會將所有球都往左移動 $x$ 個箱子，若超出範圍則會停在第 $1$ 個。更詳細來說，原本在第 $i$ 個箱子的球會移動到第 $\max(i - x, 1)$ 個箱子。
  3. 3 x，代表巴已己會將所有球都往右移動 $x$ 個箱子，若超出範圍則會停在第 $n$ 個。更詳細來說，原本在第 $i$ 個箱子的球會移動到第 $\min(i + x, n)$ 個箱子。
  4. 4 x，代表巴已己想要詢問第 $x$ 個箱子裡面有幾顆球。

你能幫幫巴已己回答所有的詢問嗎？

Input Format

輸入第一行有兩個正整數 $n, q$，代表箱子的數量與詢問的數量。

接下來 $q$ 行，每行會代表一筆操作，操作格式如題目敘述。

  • $1 \leq n \leq 10^ 9$
  • $1 \leq q \leq 5 \times 10^ 5$
  • $1 \leq x \leq n$
  • $1 \leq y \leq 10^ 9$

Output Format

對於每個詢問操作，請輸出一行，該行有一個整數代表該筆詢問的答案。

Sample Input 1

5 10
1 1 3
4 1
3 2
4 1
4 3
1 5 6
2 5
4 1
3 3
4 4

Sample Output 1

3
0
3
9
9

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~20 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 2
1 2000 262144 65536 2
2 2000 262144 65536 2
3 2000 262144 65536 2
4 2000 262144 65536 2
5 2000 262144 65536 2
6 2000 262144 65536 2
7 2000 262144 65536 2
8 2000 262144 65536 2
9 2000 262144 65536 2
10 2000 262144 65536 2
11 2000 262144 65536 2
12 2000 262144 65536 2
13 2000 262144 65536 2
14 2000 262144 65536 2
15 2000 262144 65536 2
16 2000 262144 65536 2
17 2000 262144 65536 2
18 2000 262144 65536 2
19 2000 262144 65536 2
20 2000 262144 65536 2
Submit
Back to Top