Агуулгыг алгасах

Өгөгдлийн бүтцээс $O(T(n)\log n)$-д устгах

Танд элемент нэмэхийг жинхэнэ $O(T(n))$-д зөвшөөрдөг өгөгдлийн бүтэц байгаа гэж бодъё. Энэ өгүүлэлд офлайнаар $O(T(n)\log n)$-д устгах боломж олгодог аргыг тайлбарлана.

Алгоритм

Элемент бүр нэмэлт ба устгалтын хооронд тодорхой хугацааны хэрчмүүдэд өгөгдлийн бүтцэд оршдог. Асуулгууд дээр хэрчмийн мод байгуулъя. Ямар нэг элемент амьд байх хэрчим бүр модны $O(\log n)$ зангилаанд хуваагдана. Бид бүтцийн талаар ямар нэг зүйл мэдэхийг хүсэх асуулга бүрийг харгалзах навчид тавья. Одоо бүх асуулгыг боловсруулахын тулд бид хэрчмийн мод дээр DFS ажиллуулна. Зангилаанд орохдоо бид энэ зангилаа доторх бүх элементийг нэмнэ. Дараа нь бид энэ зангилааны хүүхдүүд рүү цааш явах, эсвэл асуулгад хариулна (хэрэв зангилаа навч бол). Зангилаанаас гарахдаа бид нэмэлтүүдийг буцаах ёстой. Хэрэв бид бүтцийг $O(T(n))$-д өөрчилвөл өөрчлөлтийн стек хадгалснаар $O(T(n))$-д өөрчлөлтүүдийг буцааж болохыг анхаарна уу. Буцаалтууд amortized complexity-г эвддэгийг анхаарна уу.

Тэмдэглэл

Ямар нэг зүйл амьд байх хэрчмүүд дээр хэрчмийн мод үүсгэх санааг зөвхөн өгөгдлийн бүтцийн бодлогод биш ашиглаж болно. Доорх зарим бодлогыг үзнэ үү.

Implementation

This implementation is for the dynamic connectivity problem. It can add edges, remove edges and count the number of connected components.

struct dsu_save {
    int v, rnkv, u, rnku;

    dsu_save() {}

    dsu_save(int _v, int _rnkv, int _u, int _rnku)
        : v(_v), rnkv(_rnkv), u(_u), rnku(_rnku) {}
};

struct dsu_with_rollbacks {
    vector<int> p, rnk;
    int comps;
    stack<dsu_save> op;

    dsu_with_rollbacks() {}

    dsu_with_rollbacks(int n) {
        p.resize(n);
        rnk.resize(n);
        for (int i = 0; i < n; i++) {
            p[i] = i;
            rnk[i] = 0;
        }
        comps = n;
    }

    int find_set(int v) {
        return (v == p[v]) ? v : find_set(p[v]);
    }

    bool unite(int v, int u) {
        v = find_set(v);
        u = find_set(u);
        if (v == u)
            return false;
        comps--;
        if (rnk[v] > rnk[u])
            swap(v, u);
        op.push(dsu_save(v, rnk[v], u, rnk[u]));
        p[v] = u;
        if (rnk[u] == rnk[v])
            rnk[u]++;
        return true;
    }

    void rollback() {
        if (op.empty())
            return;
        dsu_save x = op.top();
        op.pop();
        comps++;
        p[x.v] = x.v;
        rnk[x.v] = x.rnkv;
        p[x.u] = x.u;
        rnk[x.u] = x.rnku;
    }
};

struct query {
    int v, u;
    bool united;
    query(int _v, int _u) : v(_v), u(_u) {
    }
};

struct QueryTree {
    vector<vector<query>> t;
    dsu_with_rollbacks dsu;
    int T;

    QueryTree() {}

    QueryTree(int _T, int n) : T(_T) {
        dsu = dsu_with_rollbacks(n);
        t.resize(4 * T + 4);
    }

    void add_to_tree(int v, int l, int r, int ul, int ur, query& q) {
        if (ul > ur)
            return;
        if (l == ul && r == ur) {
            t[v].push_back(q);
            return;
        }
        int mid = (l + r) / 2;
        add_to_tree(2 * v, l, mid, ul, min(ur, mid), q);
        add_to_tree(2 * v + 1, mid + 1, r, max(ul, mid + 1), ur, q);
    }

    void add_query(query q, int l, int r) {
        add_to_tree(1, 0, T - 1, l, r, q);
    }

    void dfs(int v, int l, int r, vector<int>& ans) {
        for (query& q : t[v]) {
            q.united = dsu.unite(q.v, q.u);
        }
        if (l == r)
            ans[l] = dsu.comps;
        else {
            int mid = (l + r) / 2;
            dfs(2 * v, l, mid, ans);
            dfs(2 * v + 1, mid + 1, r, ans);
        }
        for (query q : t[v]) {
            if (q.united)
                dsu.rollback();
        }
    }

    vector<int> solve() {
        vector<int> ans(T);
        dfs(1, 0, T - 1, ans);
        return ans;
    }
};

Бодлогууд