trang chủ / đề bài / dhbb23_chv_11_c

Trò chơi

Hôm nay là buổi học hè đầu tiên của lớp X, cô giáo tổ chức một trò chơi nho nhỏ để tăng sự hứng thú học tập của các bạn học sinh. Vì đây chỉ là một trò chơi nho nhỏ, nên chúng cực kỳ dễ. Và đặc biệt hơn nữa, là bạn nào chiến thắng trò chơi này sẽ có thưởng. Vì thế, các bạn học sinh ai cũng cố gắng hết sức để có thể giành chiến thắng. Nội dung trò chơi như sau:

Cô giáo đưa ra một dãy số $A$ gồm $N$ phần tử được đánh số từ $1$ đến $N$ . Giá trị ban đầu của tất cả các phần tử đều là $0$ . Cô giáo sẽ thực hiện $Q$ thao tác gồm $2$ loại, mỗi loại có nội dung như sau:

$1 x y$ : Cô giáo sẽ tăng giá trị của phần tử $A_{x}$ lên $y$ đơn vị ( $y$ có thể âm).
$2 a b$ : Cô giáo yêu cầu các bạn hãy tính tổng giá trị của tất cả các phần tử $A_{k}$ thỏa mãn: $1 \leq k \leq N$ và $k mod a = b$ .

Cô giáo yêu cầu rằng ai trả lời đúng hết các câu hỏi mới là người có khả năng giành chiến thắng. Tất cả mọi người vẫn chưa nhận ra rằng, trò chơi này khó thế nào. Chỉ có duy nhất Tèo, một bạn học giỏi thứ $Z$ lớp, thấy rằng trò này rất khó để chiến thắng. Sắp đến lúc bắt đầu trò chơi mà cậu vẫn chưa nghĩ ra cách nào để chiến thắng, thì chợt nghĩ đến bạn, thiên tài tin học.

Yêu cầu: Bạn hãy viết một chương trình để giúp Tèo chiến thắng trò chơi này nhé!

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên dương $N$ và $Q$ lần lượt là số phần tử của mảng và số thao tác của cô giáo.
Dòng thứ i trong số Q dòng tiếp theo, mỗi dòng là một trong hai thao tác:
- $1 x y$ : $1 \leq x \leq N$ , $- 1000 \leq y \leq 1000$ .
- $2 a b$ : $1 \leq a \leq N$ , $0 \leq b < a$ .

Dữ liệu ra

Gồm nhiều số nguyên, mỗi số nguyên được ghi trên một dòng là kết quả của thao tác loại $2$ , theo thứ tự xuất hiện.

Ràng buộc

$1 \leq N, Q \leq 250000$ .
Với thao tác loại $1$ : $1 \leq x \leq N$ , $- 1000 \leq y \leq 1000$ .
Với thao tác loại $2$ : $1 \leq a \leq N$ , $0 \leq b < a$ .

Subtasks

$40 %$ số test: $1 \leq N, Q \leq 5000$ .
$30 %$ số test khác: $1 \leq N, Q \leq 150000$ và $1 \leq a \leq 200$ .
$30 %$ số test còn lại: $1 \leq N, Q \leq 250000$ .

Ví dụ

Input	Output	Giải thích
5 5 1 3 3 2 3 0 2 4 3 1 4 -9 2 1 0	3 3 -6	Sau thao tác đầu, $A = (0, 0, 3, 0, 0)$ . Với $a = 3, b = 0$ chỉ có $k = 3$ , tổng là $3$ . Với $a = 4, b = 3$ chỉ có $k = 3$ , tổng là $3$ . Sau khi giảm $A_{4}$ đi $9$ , với $a = 1, b = 0$ lấy mọi phần tử: $3 - 9 = - 6$ .
6 7 1 6 5 1 2 -4 2 4 2 2 6 0 2 5 2 1 5 1000 2 3 2	1 5 -4 996	$A_{6} = 5$ , $A_{2} = - 4$ . Với $a = 4, b = 2$ : $k \in {2, 6}$ , tổng $1$ . Với $a = 6, b = 0$ : chỉ $k = 6$ (vì $k \geq 1$ ). Với $a = 5, b = 2$ : chỉ $k = 2$ . Sau khi $A_{5} = 1000$ , với $a = 3, b = 2$ : $k \in {2, 5}$ , tổng $996$ .

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 6,00một phần

Giới hạn thời gian 1.0s

Python 33.5s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, F#, Forth, Fortran, Go, Groovy, Java, Javascript, Julia, Kotlin, Lean, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, Swift, TCL, Typescript, V, Visual Basic, Zig

Đề bài

Mô tả