콘텐츠로 이동

자료 구조에서 $O(T(n)\log n)$에 삭제하기

원소를 진정한 $O(T(n))$에 추가할 수 있는 자료 구조가 있다고 가정합시다. 이 글에서는 오프라인으로 $O(T(n)\log n)$에 삭제할 수 있게 하는 기법을 설명합니다.

알고리즘

각 원소는 추가와 삭제 사이의 몇몇 시간 구간 동안 자료 구조 안에 존재합니다. 쿼리들 위에 세그먼트 트리를 만듭시다. 어떤 원소가 살아 있는 각 구간은 트리의 $O(\log n)$개 노드로 나뉩니다. 자료 구조에 대해 무언가를 알고자 하는 각 쿼리를 해당하는 리프에 넣읍시다. 이제 모든 쿼리를 처리하기 위해 세그먼트 트리에서 DFS를 수행합니다. 노드에 들어갈 때 이 노드 안에 있는 모든 원소를 추가합니다. 그런 다음 이 노드의 자식으로 더 내려가거나, (노드가 리프라면) 쿼리에 답합니다. 노드를 떠날 때에는 추가한 것을 되돌려야 합니다. 자료 구조를 $O(T(n))$에 변경한다면, 변경 사항의 스택을 유지하여 그 변경을 $O(T(n))$에 롤백할 수 있다는 점에 유의하십시오. 롤백은 분할 상환 복잡도를 깨뜨린다는 점에 유의하십시오.

참고

무언가가 살아 있는 구간들 위에 세그먼트 트리를 만드는 아이디어는 자료 구조 문제에만 사용될 수 있는 것이 아닙니다. 아래의 몇몇 문제를 참고하십시오.

구현

이 구현은 동적 연결성 문제에 대한 것입니다. 간선을 추가하고, 간선을 제거하고, 연결 요소의 개수를 셀 수 있습니다.

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;
    }
};

문제