Policy-Based Data Structures

1
#include <bits/stdc++.h>              // For convenience in CP
2
#include <ext/pb_ds/assoc_container.hpp>
3
#include <ext/pb_ds/tree_policy.hpp>
4
5
using namespace std;
6
using namespace __gnu_pbds;
7
8
// Alias for an order-statistics set of ints
9
// Key type = int, mapped type = null_type (set behavior)
10
// Comparator = less<int> (strict weak ordering)
11
// Tag = rb_tree_tag (red-black tree)
12
// Node update = tree_order_statistics_node_update (enables order stats)
13
template <class T>
14
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
15
16
int main() {
17
    ios::sync_with_stdio(false);
18
    cin.tie(nullptr);
19
20
    ordered_set<int> os; // empty
21
22
    // Insert elements (duplicates are ignored since this is a set)
23
    os.insert(10);
24
    os.insert(5);
25
    os.insert(20);
26
    os.insert(10); // ignored
27
28
    // 1) order_of_key(x): how many elements are < x
29
    cout << "order_of_key(15) = " << os.order_of_key(15) << "\n"; // {5,10,20} -> 2
30
    cout << "order_of_key(5) = " << os.order_of_key(5) << "\n";   // -> 0
31
    cout << "order_of_key(100) = " << os.order_of_key(100) << "\n"; // -> 3
32
33
    // 2) find_by_order(k): iterator to k-th smallest (0-based)
34
    for (int k = 0; k < (int)os.size(); ++k) {
35
        cout << "k=" << k << ", element=" << *os.find_by_order(k) << "\n";
36
    }
37
38
    // Erase an element and query again
39
    os.erase(10); // remove value 10
40
    cout << "After erasing 10, size=" << os.size() << "\n";
41
    if (!os.empty()) {
42
        cout << "Smallest element is now: " << *os.find_by_order(0) << "\n";
43
    }
44
45
    // Check presence (normal set interface works)
46
    cout << (os.find(20) != os.end() ? "20 present" : "20 missing") << "\n";
47
48
    return 0;
49
}
50

1
#include <bits/stdc++.h>
2
#include <ext/pb_ds/assoc_container.hpp>
3
#include <ext/pb_ds/tree_policy.hpp>
4
5
using namespace std;
6
using namespace __gnu_pbds;
7
8
template <class T>
9
using ordered_tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
10
11
// We emulate a multiset by storing (value, unique_id) so that duplicates are distinct.
12
// Comparator is lexicographic: first by value, then by id.
13
14
int main() {
15
    ios::sync_with_stdio(false);
16
    cin.tie(nullptr);
17
18
    ordered_tree<pair<int,int>> ms; // ordered multiset emulation
19
    int next_id = 0;                 // unique id for duplicates
20
21
    // Simple interactive demo: I x (insert), D x (delete one x), M (print median), Q (quit)
22
    // Example input:
23
    // I 5
24
    // I 1
25
    // I 5
26
    // M
27
    // D 5
28
    // M
29
30
    char op;
31
    while (cin >> op) {
32
        if (op == 'I') {
33
            int x; cin >> x;
34
            ms.insert({x, next_id++});
35
        } else if (op == 'D') {
36
            int x; cin >> x;
37
            // Erase a single occurrence of x if present
38
            auto it = ms.lower_bound({x, numeric_limits<int>::min()});
39
            if (it != ms.end() && it->first == x) ms.erase(it);
40
        } else if (op == 'M') {
41
            if (ms.empty()) {
42
                cout << "EMPTY\n";
43
            } else {
44
                int n = (int)ms.size();
45
                // Lower median for even n
46
                int k = (n - 1) / 2;
47
                int median = ms.find_by_order(k)->first;
48
                cout << median << "\n";
49
            }
50
        } else if (op == 'Q') {
51
            break;
52
        }
53
    }
54
55
    return 0;
56
}
57

1
#include <bits/stdc++.h>
2
#include <ext/pb_ds/assoc_container.hpp>
3
#include <ext/pb_ds/tree_policy.hpp>
4
5
using namespace std;
6
using namespace __gnu_pbds;
7
8
template <class T>
9
using ordered_tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
10
11
int main() {
12
    ios::sync_with_stdio(false);
13
    cin.tie(nullptr);
14
15
    int n; 
16
    if (!(cin >> n)) return 0;
17
    vector<long long> a(n);
18
    for (int i = 0; i < n; ++i) cin >> a[i];
19
20
    // To handle duplicates correctly, store (value, index)
21
    ordered_tree<pair<long long,int>> os;
22
    long long inv = 0;
23
24
    for (int i = 0; i < n; ++i) {
25
        // Number of elements <= a[i] is order_of_key({a[i], +INF})
26
        int le = os.order_of_key({a[i], INT_MAX});
27
        int inserted = i;
28
        int greater = inserted - le; // strictly greater to the left
29
        inv += greater;
30
        os.insert({a[i], i});
31
    }
32
33
    cout << inv << "\n";
34
    return 0;
35
}
36

1
#include <bits/stdc++.h>
2
#include <ext/pb_ds/assoc_container.hpp>
3
#include <ext/rope>
4
5
using namespace std;
6
using namespace __gnu_pbds;
7
using namespace __gnu_cxx; // for rope
8
9
// Strong 64-bit mix for pairs to reduce collisions
10
struct PairHash {
11
    size_t operator()(const pair<int,int>& p) const noexcept {
12
        uint64_t x = (static_cast<uint64_t>(static_cast<uint32_t>(p.first)) << 32) ^ static_cast<uint32_t>(p.second);
13
        x ^= 0x9e3779b97f4a7c15ULL;
14
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
15
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
16
        x = x ^ (x >> 31);
17
        return static_cast<size_t>(x);
18
    }
19
};
20
21
int main() {
22
    ios::sync_with_stdio(false);
23
    cin.tie(nullptr);
24
25
    // Part 1: gp_hash_table for counting frequency of 2D points
26
    gp_hash_table<pair<int,int>, int, PairHash> freq;
27
    vector<pair<int,int>> pts = {{1,2},{2,3},{1,2},{4,5},{2,3},{2,3}};
28
    for (auto &p : pts) freq[p]++;
29
30
    cout << "Frequencies (gp_hash_table):\n";
31
    // Use an auxiliary set to avoid duplicate prints
32
    set<pair<int,int>> printed(pts.begin(), pts.end());
33
    for (auto &p : printed) {
34
        cout << '(' << p.first << ',' << p.second << ") -> " << freq[p] << '\n';
35
    }
36
37
    // Part 2: rope for efficient text edits
38
    rope<char> r;
39
    r.append("hello");
40
    r.push_back(' ');
41
    r.append("world");              // r = "hello world"
42
    r.insert(5, ", brave new");    // insert after "hello"
43
    r.erase(0, 1);                   // erase first character
44
    rope<char> sub = r.substr(0, 12); // first 12 characters
45
46
    cout << "\nRope full text: ";
47
    for (int i = 0; i < (int)r.size(); ++i) cout << r[i];
48
    cout << "\nRope substring: ";
49
    for (int i = 0; i < (int)sub.size(); ++i) cout << sub[i];
50
    cout << '\n';
51
52
    return 0;
53
}
54