RPG

RPG

الأولمبياد الوطني للبرمجة 2026 - المسابقة الرابعة، اليوم الأول

الزمن المحدد: 1 ثانية الذاكرة المحددة: 256 ميجابايت

أنت تلعب لعبة تحتوي على \(N\) وحوش مرتبة في صف. قوة الوحش رقم \(i\) هي \(A_i\).

في البداية، تكون قوتك مساوية لـ \(0\). تقاتل الوحوش من اليسار إلى اليمين. إذا واجهت وحشًا قوته أكبر تمامًا من قوتك الحالية، فإنك تهزمه، وتصبح قوتك مساوية لقوته، ثم تعيد البدء فورًا من الوحش الأول. تستمر هذه العملية حتى تتمكن من المرور عبر الصف كله دون أن تزيد قوتك.

عدد المرات التي تعيد فيها البدء يُسمى الإجابة.

أُعطيت أيضًا \(Q\) تحديثات. كل تحديث يكون على الشكل \((i,k)\)، ويعني أن قوة الوحش رقم \(i\) تزداد بمقدار \(k\).

ملاحظة: تستمر آثار التحديثات بين الاستعلامات، لكن قوتك تعود إلى \(0\) قبل كل استعلام.

بعد كل تحديث، اطبع الإجابة.

المدخلات

يحتوي السطر الأول على عددين صحيحين \(N\) و\(Q\)، حيث \(1 \le N, Q \le 2 \cdot 10^5\).

يحتوي السطر الثاني على \(N\) عددًا صحيحًا \(A_1, A_2, \dots, A_N\)، حيث \(1 \le A_i \le 10^9\).

يحتوي كل واحد من الأسطر الـ \(Q\) التالية على عددين صحيحين \(i\) و\(k\)، حيث \(1 \le i \le N,\quad 1 \le k \le 10^9\).

لكل تحديث، زِد قيمة \(A_i\) بمقدار \(k\).

المخرجات

لكل استعلام، اطبع عددًا صحيحًا واحدًا: عدد مرات إعادة البدء المطلوبة بعد تطبيق التحديث.

التقييم

المجموعة	القيود	النقاط
\(1\)	\(N, Q \le 200\)	\(13\)
\(2\)	\(Q = 1\)	\(17\)
\(3\)	\(i = 1\)	\(23\)
\(4\)	\(i = N\)	\(11\)
\(5\)	قيمة \(i\) ثابتة في جميع الاستعلامات	\(7\)
\(6\)	—	\(29\)

أمثلة

المدخلات

3 3
3 4 5
3 1
2 3
1 10

المخرجات

3
2
1

الملاحظات

• بعد التحديث الأول \((3,1)\)، تصبح المصفوفة \([3,4,6]\).

  • الجولة الأولى: تتغير القوة من \(0\) إلى \(3\).
  • الجولة الثانية: تتغير القوة من \(3\) إلى \(4\).
  • الجولة الثالثة: تتغير القوة من \(4\) إلى \(6\).
  • الجولة الرابعة: لا يحدث أي تغيير، فتتوقف العملية.

  زادت القوة \(3\) مرات، لذلك الإجابة هي \(3\).

• بعد التحديث الثاني \((2,3)\)، تصبح المصفوفة \([3,7,6]\).

  • الجولة الأولى: تتغير القوة من \(0\) إلى \(3\).
  • الجولة الثانية: تتغير القوة من \(3\) إلى \(7\).
  • الجولة الثالثة: لا يحدث أي تغيير، فتتوقف العملية.

  زادت القوة \(2\) مرتين، لذلك الإجابة هي \(2\).

• بعد التحديث الثالث \((1,10)\)، تصبح المصفوفة \([13,7,6]\).

  • الجولة الأولى: تتغير القوة من \(0\) إلى \(13\).
  • الجولة الثانية: لا يحدث أي تغيير، فتتوقف العملية.

  زادت القوة مرة واحدة، لذلك الإجابة هي \(1\).

الحل

ترفع كل إعادة تشغيل القوة إلى أكبر قيمة بادئة صارمة تالية، ولذلك تساوي الإجابة عدد القيم القصوى البادئة الصارمة. احفظ فهارسها في مجموعة مرتبة. بعد زيادة \(A_i\): إذا كان \(i\) قيمة قصوى بادئة فيبقى كذلك؛ وإلا يصبح كذلك فقط إذا تجاوز القيمة القصوى السابقة؛ وإذا صار قيمة قصوى فاحذف كل قيمة قصوى لاحقة لا تتجاوز \(A_i\). لا يُدرج فهرس أو يُحذف إلا بعد تحديث، لذا التعقيد الكلي \(O((N+Q)\log N)\) والذاكرة \(O(N)\).

#include <iostream>
#include <set>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> a(n);
    set<int> records;
    long long maximum = -1;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] > maximum) {
            maximum = a[i];
            records.insert(i);
        }
    }

    while (q--) {
        int index;
        long long increase;
        cin >> index >> increase;
        index--;
        a[index] += increase;

        auto it = records.lower_bound(index);

        if (it == records.end() || *it != index) {
            int previous = *prev(it);
            if (a[index] > a[previous]) {
                it = records.insert(index).first;
            } else {
                cout << records.size() << '\n';
                continue;
            }
        }

        auto next = std::next(it);
        while (next != records.end() && a[*next] <= a[index]) {
            next = records.erase(next);
        }

        cout << records.size() << '\n';
    }
}