«إنه خارج عن القانون وهو مشهور، Andrii Popa الشجاع.

ليلاً ونهاراً يمتطي جواده، يأخذ إتاوته من الطريق الرئيسي، وفي كل مكان في البلاد يفرّ صائدو اللصوص بأقصى ما يستطيعون من سرعة»

— "Andrii Popa"، Phoenix

لدى Ghiță متتالية $S$ مفهرسة بدءاً من $0$ تتكون من $N$ من الأوزان الصحيحة الموجبة. وبما أنه ملك جبال الكاربات، فإنه يريد إنشاء شجرة ثنائية تحمل عقدها الفهارس $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ță للمثال السابق هو: