Universal Cup Judging System

Universal Cup

Time Limit: 4.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

Little L có một lưới tam giác đều, trong đó mỗi đường lưới là một đoạn thẳng nối các điểm chia $n$ phần bằng nhau tương ứng trên các cạnh kề nhau. Những đường lưới này chia tam giác đều thành nhiều tam giác đều nhỏ hơn bằng nhau.

Đối với mỗi giao điểm của các đường lưới trong hình, ta biểu diễn nó bằng tọa độ $(x, y)$. Tọa độ $x$ từ trên xuống dưới có giá trị từ $1$ đến $n + 1$. $x = 1$ biểu thị điểm cao nhất, trong khi $x = n + 1$ biểu thị đường đáy. Ở hàng thứ $i$, tọa độ $y$ của các điểm lưới từ trái sang phải có giá trị từ $1$ đến $i$.

Trong lưới tam giác có một số tam giác đều, có thể có hướng xuôi (đỉnh hướng lên) hoặc ngược (đỉnh hướng xuống). Với mỗi hướng của tam giác, ta biểu diễn nó bằng ba số $x, y, d$. Ở đây, $(x, y)$ biểu thị tọa độ của đỉnh đối diện với cạnh song song với đường đáy của lưới, và $d$ biểu thị độ dài cạnh của nó (độ dài của đoạn thẳng).

Ví dụ, trong hình bên dưới, tam giác đều màu xanh dương là một tam giác xuôi, với $(x, y, d) = (4, 2, 3)$. Tam giác đều màu vàng là một tam giác ngược, với $(x, y, d) = (6, 3, 2)$.

Bây giờ, trên mỗi ô lưới tam giác đều nhỏ đơn vị (một tam giác đều có độ dài cạnh bằng $1$, bất kể hướng nào), có viết một con số. Ban đầu, tất cả các số trên lưới đều bằng $0$. Little L sẽ thực hiện các thao tác sau:

  • Chọn một tam giác đều và cộng $w$ vào tất cả các số trên các ô lưới nằm bên trong nó.
  • Chọn một tam giác đều và truy vấn tổng của tất cả các số trên các ô lưới nằm bên trong nó.

Cậu ấy hy vọng bạn có thể tính toán câu trả lời cho mỗi thao tác truy vấn. Vì Little L không thích các số lớn, bạn chỉ cần in ra kết quả của đáp án theo modulo $2^{32}$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).

$q$ dòng tiếp theo, mỗi dòng biểu thị một thao tác.

Mỗi dòng bắt đầu bằng năm số $opt, type, x, y, d$ ($opt \in \{1, 2\}, type \in \{0, 1\}, 1 \le x \le n + 1, 1 \le y \le x, 1 \le d \le n$). $opt$ biểu thị loại thao tác, trong đó $opt = 1$ là thao tác sửa đổi và $opt = 2$ là thao tác truy vấn. $type$ cho biết loại tam giác của thao tác này, trong đó $type = 0$ là tam giác xuôi và $type = 1$ là tam giác ngược. $x, y, d$ mô tả tam giác này. Nếu $opt = 1$, sẽ có thêm một số $w$ ($0 \le w < 2^{32}$) cho biết giá trị được cộng thêm trong thao tác sửa đổi này.

Đảm bảo rằng tất cả các tam giác trong dữ liệu vào đều có diện tích khác không và là các tam giác hợp lệ nằm hoàn toàn bên trong tam giác lớn.

Dữ liệu ra

Với mỗi truy vấn có $opt = 2$, in ra một số duy nhất trên một dòng mới, biểu thị tổng trong vùng đó theo modulo $2^{32}$.

Ví dụ

Dữ liệu vào 1

5 5
1 0 3 3 2 2
1 1 6 4 2 3
2 0 1 1 5
2 0 3 2 3
2 1 5 3 2

Dữ liệu ra 1

20
11
3

Dữ liệu vào 2

10 10
1 0 1 1 5 2
1 1 3 2 1 6
1 1 6 4 2 1
2 0 10 3 1
2 1 5 2 1
2 1 6 4 2
1 0 7 7 1 7
1 1 9 3 1 3
1 0 9 5 2 4
2 0 6 1 2

Dữ liệu ra 2

0
2
12
0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.