Universal Cup Judging System

Universal Cup

Limite de temps : 4.0 s Limite de mémoire : 1024 MB Points totaux : 100 Hackable ✓
Statistiques

Mały L ma siatkę w kształcie trójkąta równobocznego, w której każda linia siatki jest odcinkiem łączącym odpowiednie punkty podziału sąsiednich boków na $n$ równych części. Linie te dzielą trójkąt równoboczny na pewną liczbę przystających mniejszych trójkątów równobocznych.

Każdy punkt przecięcia linii siatki na rysunku oznaczamy współrzędnymi $(x, y)$. Współrzędna $x$ od góry do dołu przyjmuje wartości od $1$ do $n + 1$. $x = 1$ oznacza najwyższy punkt, natomiast $x = n + 1$ oznacza dolną linię. W $i$-tym wierszu współrzędne $y$ punktów siatki od lewej do prawej przyjmują wartości od $1$ do $i$.

W trójkątnej siatce znajduje się pewna liczba trójkątów równobocznych, które mogą być skierowane wierzchołkiem w górę (proste) lub w dół (odwrócone). Niezależnie od orientacji, trójkąt opisujemy trzema liczbami $x, y, d$. Tutaj $(x, y)$ oznacza współrzędne wierzchołka przeciwległego do jego boku równoległego do dolnej linii siatki, natomiast $d$ oznacza długość jego boku (długość odcinka).

Na przykład na poniższym rysunku niebieski trójkąt równoboczny jest trójkątem prostym o parametrach $(x, y, d) = (4, 2, 3)$. Żółty trójkąt równoboczny jest trójkątem odwróconym o parametrach $(x, y, d) = (6, 3, 2)$.

Teraz na każdym jednostkowym małym trójkącie równobocznym siatki (trójkącie równobocznym o długości boku $1$, niezależnie od orientacji) zapisana jest liczba. Początkowo wszystkie liczby na polach siatki są równe $0$. Mały L wykona następujące operacje:

  • Wybierz trójkąt równoboczny i dodaj $w$ do wszystkich liczb na polach siatki wewnątrz niego.
  • Wybierz trójkąt równoboczny i zapytaj o sumę wszystkich liczb na polach siatki wewnątrz niego.

Ma on nadzieję, że obliczysz odpowiedź dla każdej operacji zapytania. Ponieważ Mały L nie lubi dużych liczb, wystarczy wypisać wynik odpowiedzi modulo $2^{32}$.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).

Kolejne $q$ wierszy opisuje poszczególne operacje.

Każdy wiersz zaczyna się od pięciu liczb $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$ oznacza typ operacji, gdzie $opt = 1$ to operacja modyfikacji, a $opt = 2$ to operacja zapytania. $type$ określa typ trójkąta w tej operacji, gdzie $type = 0$ oznacza trójkąt prosty, a $type = 1$ oznacza trójkąt odwrócony. Liczby $x, y, d$ opisują ten trójkąt. Jeśli $opt = 1$, w wierszu znajduje się dodatkowa liczba $w$ ($0 \le w < 2^{32}$), oznaczająca wartość dodawaną podczas tej operacji modyfikacji.

Gwarantowane jest, że wszystkie trójkąty na wejściu mają niezerowe pole i są poprawnymi trójkątami całkowicie zawartymi wewnątrz dużego trójkąta.

Wyjście

Dla każdego zapytania z $opt = 2$ wypisz w nowym wierszu jedną liczbę oznaczającą sumę w danym obszarze modulo $2^{32}$.

Przykład

Wejście 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

Wyjście 1

20
11
3

Wejście 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

Wyjście 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.