The Chtholly Tree: A Brute Force Data Structure for Competitive Programming

The Chtholly Tree, invented by Algha_Porthos, is a powerful brute force data structure for interval assignment operations on random data. Although it may not resemble a traditional tree data structure, it is commonly implemented using std::set which is based on a red-black tree. The Chtholly Tree has a complexity of O(n log log n) with random data.

To understand how the Chtholly Tree works and its potential applications in competitive programming, check out Algha_Porthos's original blog post here.

Here is an example implementation of the Chtholly Tree for finding the number of overlapping intervals:

const int maxn = 1e6;
struct Segment{
    int l, r;
} a[maxn];
struct Node{
    int ls, rs, cnt;
} t[maxn * 64];
int rt[maxn], tot, n, m;

inline void upd(int& now, int pre, int l, int r, int x){
    now = ++tot; t[now] = t[pre];
    t[now].cnt++;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) upd(t[now].ls, t[pre].ls, l, mid, x);
    else upd(t[now].rs, t[pre].rs, mid + 1, r, x);
}

inline int query(int u, int v, int l, int r, int L, int R){
    if (L > R) return 0;
    if (L <= l && r <= R) return t[v].cnt - t[u].cnt;
    int mid = (l + r) >> 1, res = 0;
    if (L <= mid) res += query(t[u].ls, t[v].ls, l, mid, L, R);
    if (R > mid) res += query(t[u].rs, t[v].rs, mid + 1, r, L, R);
    return res;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r;
        a[i] = {l, r};
    }
    sort(a + 1, a + 1 + n, [](Segment& a, Segment& b) {
        if (a.r != b.r) return a.r < b.r;
        return a.l > b.l;
    });
    for (int i = 1; i <= n; i++) {
        upd(rt[i], rt[i - 1], 1, m, a[i].l);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += query(rt[1], rt[i], 1, m, a[i].l, a[i].r);
    }
    cout << ans << endl;
    return 0;
}

By using the Chtholly Tree for interval assignment operations on random data, you can optimize your competitive programming solutions and achieve faster runtime. Keep in mind that the Chtholly Tree may not be suitable for all situations, so it is important to understand when and how to use it effectively.

For more information on competitive programming and data structures, check out resources like Codeforces and Topcoder.