Universal Cup Judging System

Universal Cup

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

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.