Universal Cup Judging System

Universal Cup

Süre Sınırı: 4.0 s Bellek Sınırı: 1024 MB Toplam puan: 100 Hack'lenebilir ✓
İstatistikler

لدى Little L شبكة مثلثية منتظمة، حيث كل خط في الشبكة هو قطعة مستقيمة تصل بين نقاط التقسيم الـ $n$ المتناظرة للأضلاع المتجاورة. تقسم خطوط الشبكة هذه المثلث المتساوي الأضلاع إلى عدة مثلثات متساوية أضلاع أصغر ومتطابقة.

لكل نقطة تقاطع لخطوط الشبكة في الشكل، نمثلها بالإحداثيين $(x, y)$. يتراوح الإحداثي $x$ من الأعلى إلى الأسفل بين $1$ و $n + 1$. يمثل $x = 1$ النقطة العليا، بينما يمثل $x = n + 1$ الخط السفلي. بالنسبة للصف ذي الترتيب $i$، تتراوح الإحداثيات $y$ لنقاط الشبكة من اليسار إلى اليمين بين $1$ و $i$.

يوجد في الشبكة المثلثية عدة مثلثات متساوية الأضلاع، قد تكون موجهة للأعلى (معتدلة) أو للأسفل (مقلوبة). لكل اتجاه للمثلث، نمثله بثلاثة أعداد $x, y, d$. هنا، $(x, y)$ يمثل إحداثيات الرأس المقابل لضلع المثلث الموازي للخط السفلي للشبكة، و $d$ يمثل طول ضلعه (طول القطعة المستقيمة).

على سبيل المثال، في الشكل أدناه، المثلث المنتظم الأزرق هو مثلث معتدل بمعاملات $(x, y, d) = (4, 2, 3)$. والمثلث المنتظم الأصفر هو مثلث مقلوب بمعاملات $(x, y, d) = (6, 3, 2)$.

الآن، لكل خلية مثلثية منتظمة صغيرة واحدية (مثلث متساوي الأضلاع طول ضلعه $1$، بغض النظر عن اتجاهه)، يوجد عدد مكتوب عليها. في البداية، جميع الأعداد على الشبكة تساوي $0$. سيقوم Little L بإجراء العمليات التالية:

  • اختيار مثلث منتظم وإضافة $w$ إلى جميع الأعداد الموجودة في خلايا الشبكة داخله.
  • اختيار مثلث منتظم والاستعلام عن مجموع جميع الأعداد الموجودة في خلايا الشبكة داخله.

يأمل أن تتمكن من حساب الإجابة لكل عملية استعلام. وبما أن Little L لا يحب الأعداد الكبيرة، فما عليك سوى طباعة نتيجة الإجابة بباقي القسمة على $2^{32}$.

الإدخال

يحتوي السطر الأول من الإدخال على عددين صحيحين $n, q$ ($2 \le n \le 10^5, 1 \le q \le 10^5$).

تمثل الأسطر الـ $q$ التالية عملية واحدة في كل سطر.

يبدأ كل سطر بخمسة أعداد $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$ نوع العملية، حيث $opt = 1$ عملية تعديل، و $opt = 2$ عملية استعلام. يشير $type$ إلى نوع المثلث في هذه العملية، حيث $type = 0$ للمثلث المعتدل، و $type = 1$ للمثلث المقلوب. وتصف $x, y, d$ هذا المثلث. إذا كان $opt = 1$، فهناك عدد إضافي $w$ ($0 \le w < 2^{32}$) يشير إلى العدد المضاف خلال عملية التعديل هذه.

من المضمون أن جميع المثلثات المدخلة لها مساحة غير صفرية وهي مثلثات صالحة محتواة بالكامل داخل المثلث الأكبر.

الإخراج

لكل استعلام فيه $opt = 2$، اطبع عدداً واحداً في سطر جديد يمثل المجموع داخل المنطقة بباقي القسمة على $2^{32}$.

أمثلة

الإدخال 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

الإخراج 1

20
11
3

الإدخال 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

الإخراج 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.