Universal Cup Judging System

Universal Cup

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

Little L possède une grille triangulaire régulière, où chaque ligne de la grille est un segment reliant les $n$ points de division correspondants des côtés adjacents. Ces lignes divisent le triangle équilatéral en plusieurs petits triangles équilatéraux congruents.

Chaque point d'intersection des lignes de la grille sur la figure est représenté par ses coordonnées $(x, y)$. La coordonnée $x$, de haut en bas, varie de $1$ à $n + 1$. $x = 1$ représente le point le plus haut, tandis que $x = n + 1$ représente la ligne du bas. Pour la $i$-ème ligne, les coordonnées $y$ des points de la grille, de gauche à droite, varient de $1$ à $i$.

Dans la grille triangulaire, on considère plusieurs triangles équilatéraux, qui peuvent être orientés vers le haut (droits) ou vers le bas (inversés). Quelle que soit son orientation, un triangle est représenté par trois nombres $x, y, d$. Ici, $(x, y)$ représente les coordonnées du sommet opposé à son côté parallèle à la ligne du bas de la grille, et $d$ représente la longueur de son côté (la longueur du segment).

Par exemple, dans la figure ci-dessous, le triangle équilatéral bleu est un triangle droit avec $(x, y, d) = (4, 2, 3)$. Le triangle équilatéral jaune est un triangle inversé avec $(x, y, d) = (6, 3, 2)$.

Maintenant, un nombre est inscrit sur chaque petit triangle équilatéral unitaire de la grille (un triangle équilatéral de côté $1$, quelle que soit son orientation). Initialement, tous les nombres sur la grille valent $0$. Little L va effectuer les opérations suivantes :

  • Choisir un triangle équilatéral et ajouter $w$ à tous les nombres des cases situées à l'intérieur.
  • Choisir un triangle équilatéral et demander la somme de tous les nombres des cases situées à l'intérieur.

Il espère que vous pourrez calculer la réponse pour chaque opération de requête. Comme Little L n'aime pas les grands nombres, il vous suffit d'afficher le résultat modulo $2^{32}$.

Entrée

La première ligne de l'entrée contient deux entiers $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).

Les $q$ lignes suivantes représentent chacune une opération.

Chaque ligne commence par cinq nombres $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$ représente le type d'opération, où $opt = 1$ est une opération de modification et $opt = 2$ est une opération de requête. $type$ indique le type de triangle pour cette opération, où $type = 0$ correspond à un triangle droit et $type = 1$ à un triangle inversé. $x, y, d$ décrivent ce triangle. Si $opt = 1$, il y a un nombre supplémentaire $w$ ($0 \le w < 2^{32}$) qui indique la valeur ajoutée lors de cette opération de modification.

Il est garanti que tous les triangles donnés en entrée ont une aire non nulle et sont des triangles valides entièrement contenus dans le grand triangle.

Sortie

Pour chaque requête avec $opt = 2$, affichez un seul nombre sur une nouvelle ligne, représentant la somme dans la zone modulo $2^{32}$.

Exemples

Entrée 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

Sortie 1

20
11
3

Entrée 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

Sortie 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.