`ordered_set`

ordered_set هي set ولكن مع وظيفتين إضافيتين:

find_by_order(k): تقوم بإرجاع مؤشراً إلى العنصر بترتيب k من الأصغر إلى الأكبر (بترقيم يبدأ من 0) بزمن قدره \(O(\log n)\).
order_of_key(x): تقوم بإرجاع عدد العناصر الأصغر من x بزمن قدره \(O(\log n)\).

Implementation

لكي نتمكن من إنشاء ordered set يجب أن نكتب ما يلي في النطاق العام:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

الآن أصبحنا جاهزين لاستخدامها. لإنشاء ordered set نكتب ببساطة ordered_set<T>، حيث T هو النوع المطلوب (مثلًا int، long long، string، إلخ).

Sliding Window Median

CSES easy

لديك مصفوفة \(x\) تحتوي على \(n\) عنصرًا وقيمة \(k\). اطبع الوسيط لكل المصفوفات الجزئية بطول \(k\).

الوسيط هو العنصر الأوسط بعد ترتيب العناصر. إذا كان عدد العناصر زوجيًا، فهناك وسيطان محتملان ونفترض أن الوسيط هو القيمة الصغرى بينهما.

Solution

يمكننا حل هذه المسألة باستخدام ordered_set من خلال تطبيق نافذة منزلقة على جميع المصفوفات الجزئية بطول \(k\). لكل نافذة، نجد العنصر بترتيب \(\frac{k}{2}\) من الأصغر إلى الأكبر باستخدام find_by_order(k/2)
(لاحظ أنه إذا كان \(k\) زوجيًا فإننا نأخذ بدلًا من ذلك k/2 - 1).

مثل set، فإن ordered_set لا تسمح بالتكرارات. لحل ذلك، نمثل المصفوفة الأصلية كأزواج، حيث يكون العنصر الأول هو القيمة
والعنصر الثاني هو موقعها، مما يضمن أن جميع العناصر مختلفة.

نظرًا لأننا نجري عملية إدخال واحدة وحذف واحدة مع كل تحريك للنافذة،
فإن التعقيد الزمني الكلي هو \(O(n \log n)\).

#include <iostream>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int main() {
    int n, k;
    cin >> n >> k;

    pair<int, int> a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i].first;
        a[i].second  = i;
    }

    ordered_set<pair<int ,int> > os;

    // أدخل النافذة الأولى
    for (int i = 0 ; i < k; i++){
        os.insert(a[i]);
    }

    // أوجد الوسيط للنافذة الأولى
    int median;
    if (k % 2 == 0){
        median = k/2 - 1;
    }
    else{
        median = k/2;
    }

    pair<int ,int> ans = *os.find_by_order(median);
    cout << ans.first << ' ';

    //تحرك عبر جميع النوافذ
    for( int i = 0 ; i < n - k ; i++){
        //اذهب للنافذة التالية
        // احذف القيمة الاولى في الهافذة
        os.erase(a[i]);

        // اضف القيمة التي بعد آخر قيمة في النافذة
        os.insert(a[i + k]);

        // اطبع الحل للنافذة الحالية
        pair<int , int> ans = *os.find_by_order(median);
        cout << ans.first << ' ';
    }

}