“เขาคือจอมโจรนอกกฎหมายผู้เลื่องชื่อ Andrii Popa ผู้กล้าหาญ

ทั้งวันทั้งคืนเขาควบม้าไป เก็บค่าคุ้มครองจากถนนสายหลัก และทุกหนแห่งทั่วทั้งแผ่นดิน เหล่าผู้ล่าโจรต่างวิ่งหนีสุดชีวิตเท่าที่จะทำได้”

— “Andrii Popa”, Phoenix

Ghiță มีลำดับ $S$ ที่เริ่มนับดัชนีจาก $0$ ซึ่งประกอบด้วยน้ำหนักจำนวนเต็มบวก $N$ จำนวน เนื่องจากเขาเป็นราชาแห่งเทือกเขาคาร์เพเทียน เขาจึงต้องการสร้างต้นไม้แบบทวิภาค (binary tree) ที่มีปมหมายเลข $0, 1, \ldots, N - 1$ โดยสอดคล้องกับเงื่อนไขต่อไปนี้:

• การท่องต้นไม้แบบอินออร์เดอร์ (inorder traversal) จะให้ลำดับของปมเรียงตามดัชนีจากน้อยไปมาก การท่องแบบอินออร์เดอร์ของต้นไม้แบบทวิภาคประกอบด้วยการท่องแบบอินออร์เดอร์ของต้นไม้ย่อยที่มีรากเป็นลูกซ้ายของราก (หากมีลูกซ้ายอยู่) ตามด้วยดัชนีของราก และตามด้วยการท่องแบบอินออร์เดอร์ของต้นไม้ย่อยที่มีรากเป็นลูกขวาของราก (หากมีลูกขวาอยู่)
• ถ้าปม $x$ เป็นพ่อของปม $y$ แล้ว $S_x$ จะหาร $S_y$ ลงตัว

ขอทบทวนว่าต้นไม้แบบทวิภาคคือโครงสร้างข้อมูลแบบต้นไม้ที่แต่ละปมมีลูกได้ไม่เกินสองปม ซึ่งเรียกว่าลูกซ้ายและลูกขวา

โชคร้ายที่จอมโจรผู้โด่งดัง Andrii Popa ได้ขโมยลำดับ $S$ ไป ทำให้ Ghiță ไม่สามารถเข้าถึงลำดับนั้นได้โดยตรงอีกต่อไป ด้วยเทคโนโลยีขั้นสูง (โทรศัพท์มือถือของเขา) สำหรับลำดับย่อยติดกัน $[a, b]$ และ $[c, d]$ ใด ๆ ของ $S$ เขาสามารถตรวจสอบได้ว่า $\gcd[a, b]$ เท่ากับ $\gcd[c, d]$ หรือไม่ เมื่อ $\gcd[x, y]$ คือตัวหารร่วมมากของ $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$ แต่น่าเสียดายที่เทคโนโลยีนี้มีราคาค่อนข้างแพง — หาก Ghiță ใช้งานมากกว่า $Q$ ครั้ง เขาจะต้องจ่ายค่าปรับจำนวนมาก จงช่วยเขาสร้างต้นไม้ที่ต้องการโดยใช้เทคโนโลยีนี้ไม่เกิน $Q$ ครั้ง รับประกันว่าสามารถทำได้เสมอ คำตอบที่ถูกต้องใด ๆ จะได้รับการยอมรับทั้งหมด

การโต้ตอบ

ผู้เข้าแข่งขันต้องรวมไฟล์ส่วนหัว popa.h (สำหรับ C / C++) หรือเขียนโปรแกรม popa.pas (สำหรับ Pascal) ผู้เข้าแข่งขันต้องเขียนฟังก์ชันต่อไปนี้:

int solve(int N, int* Left, int* Right);

function solve(N: LongInt, var Left, Right: array of LongInt): LongInt;

ฟังก์ชันนี้ต้องคืนค่ารากของต้นไม้ และกำหนดค่า $\text{Left}_i$ กับ $\text{Right}_i$ ให้เป็นลูกซ้ายและลูกขวาของปม $i$ ตามลำดับ หากปม $i$ ไม่มีลูกซ้าย ค่า $\text{Left}_i$ ต้องเป็น $-1$ หากปม $i$ ไม่มีลูกขวา ค่า $\text{Right}_i$ ต้องเป็น $-1$ ทั้งนี้ Left และ Right ชี้ไปยังอาร์เรย์สองตัวที่มีขนาดเท่ากับ $N$ พอดีซึ่งถูกจองหน่วยความจำไว้เรียบร้อยแล้ว

ฟังก์ชัน solve อาจถูกเรียกใช้ ไม่เกิน $5$ ครั้ง ในการรันหนึ่งครั้ง เราขอแนะนำให้ระมัดระวังในการใช้ตัวแปรโกลบอล

ผู้เข้าแข่งขันสามารถเรียกใช้ฟังก์ชันต่อไปนี้ได้:

int query(int a, int b, int c, int d);

function query(a, b, c, d: LongInt): LongInt;

ฟังก์ชันนี้จะคืนค่า $1$ ก็ต่อเมื่อ $\gcd[a, b]$ เท่ากับ $\gcd[c, d]$ โดยที่ $0 \le a \le b < N$ และ $0 \le c \le d < N$ และจะคืนค่า $0$ ในกรณีอื่น

งานย่อย

งานย่อยที่ 1 (37 คะแนน)

• $N = 100$
• $Q = 10000$

งานย่อยที่ 2 (24 คะแนน)

• $N = 1000$
• $Q = 20000$

งานย่อยที่ 3 (39 คะแนน)

• $N = 1000$
• $Q = 2000$

ตัวอย่าง

ตัวอย่างของการโต้ตอบสำหรับ $S = [12, 4, 16, 2, 2, 20]$ คือ:

หมายเหตุ

ตัวอย่างของต้นไม้ในแบบที่ Ghiță ต้องการสำหรับตัวอย่างก่อนหน้าคือ: