线段树分治（P5227）

FLY_lai · 2023-08-20 08:43:01 · 题解

这是一种线段树的高级玩法：在时间轴上运用。每个时间节点作为一个叶子，在一个时间区间内的标记，就可以影响到这个区间内的所有时刻。

题目传送门

建立一颗基于询问的线段树，也就是说线段树的每个结点都代表区间内的一些询问。

因为删除操作不好搞，我们反向考虑，求每个询问存在哪些边。

我们可以对每条边，求出它是否在某个询问中存在。最终我们可能求出若干个“存在区间”。例如一共有十个询问，e 在第二、六、九个询问中被删除了，e 的存在区间就是 [1,1],[3,5],[10,10] 。

求出每条边的存在区间后，我们在线段树上打标记，操作和正常的 modify 一样。把所有存在区间拆分成若干个小区间，然后在这些小区间上标记边 e 存在。

所有边都打完标记后，我们发现一个神奇的事情：叶子结点到根的路径上所有节点的标记，就是这个叶子结点存在的边。（一个叶子结点代表一个询问）

例如在 [1,1] 标记 e_1，[1,2] 标记 e_2，[1,4] 标记 e_4,e_6，则询问一就存在 e_1,e_2,e_4,e_6。（注意是存在）

于是可以通过一次 DFS，求出每个叶子结点存在的边。更进一步，我们可以使用可撤销并查集来维护 DFS 过程中的连通性。每到一个结点，并查集内加入结点标记的所有边；等到回溯的时候，把所有操作撤销。

搜索到叶子结点的时候，可以通过并查集快速判断是否图连通。

另外：其实这个做法并不需要建立线段树，只需要对每个结点开一个标记数组即可，注意是数组，因为一个结点可能标记多条边。

注意！！！可撤销并查集没有生效的操作，不要当作生效了给多次 undo 了！

代码加了注释。

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;

int n, m, q;
pair<int, int> e[2 * N]; //边数组 

int fa[N], sz[N]; //可撤销并查集板子 
struct OPT {
    int x, y, fax, fay, szx, szy;
    OPT(){}
    OPT(int a, int b, int c, int d, int e, int f) {
        x = a;
        y = b;
        fax = c;
        fay = d;
        szx = e;
        szy = f;
    }
};
stack<OPT> stk;
void init() {
    for (int i = 1; i <= n; i++)
        fa[i] = i, sz[i] = 1;
}
int fnd(int x) {
    if (x == fa[x])
        return x;
    return fnd(fa[x]);
}
void unn(int x, int y) {
    x = fnd(x), y = fnd(y);
    if (sz[x] > sz[y])
        swap(x, y);
    stk.push(OPT{x, y, fa[x], fa[y], sz[x], sz[y]});
    fa[x] = y;
    sz[y] += sz[x];
}
void undo() {
    if (stk.empty())
        return ;
    OPT opt = stk.top();
    stk.pop();
    fa[opt.x] = opt.fax;
    fa[opt.y] = opt.fay;
    sz[opt.x] = opt.szx;
    sz[opt.y] = opt.szy;
}

vector<pair<int, int> > tag[4 * N]; //每个结点的tag数组，pair里面存的是边 
vector<int> tms[2 * N];//tms[i]里保存了第i条边在哪些询问中删除 
vector<pair<int, int> > rg[2 * N]; //rg[i]保存第i条边的所有存在区间 

void mdf(int x, int lx, int rx, int l, int r, pair<int, int> v) { //在第l~r个询问上标记v，v.first/second 存的是边的两端 
    if (l <= lx && rx <= r) { //和线段树类似 
        tag[x].push_back(v); //当前节点存在边v 
        return ;
    }
    if (l >= rx || lx >= r)
        return ;
    int m = (lx + rx) / 2;
    mdf(x * 2, lx, m, l, r, v);
    mdf(x * 2 + 1, m, rx, l, r, v);
}

bool ans[N]; //每个询问的答案 

void dfs(int x, int lx, int rx) { //搜索，过程中顺路维护结点连通性 
    int cnt = 0; //cnt记录有多少次有效操作，避免撤销时撤销过多次 
    for (int i = 0; i < tag[x].size(); i++) {
        if (fnd(tag[x][i].first) != fnd(tag[x][i].second)) { //这表明是有效操作 
            unn(tag[x][i].first, tag[x][i].second);
            cnt++;
        }
    }
    if (lx + 1 == rx) { //到叶子了，判断连通性 
        ans[lx] = (sz[fnd(1)] == n ? true : false); 
        for (int i = 0; i < cnt; i++) { //即使是叶子结点，也不要忘记撤销叶子的tag 
            undo();
        }
        return ;
    }
    int m = (lx + rx) / 2;

    dfs(x * 2, lx, m); //递归到左右儿子搜索 
    dfs(x * 2 + 1, m, rx);
    for (int i = 0; i < cnt; i++) //撤销tag 
        undo();
}

int main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> e[i].first >> e[i].second;
    }
    cin >> q;
    for (int i = 1; i <= m; i++)
        rg[i].push_back(make_pair(1, q)); //初始所有边在询问[1,q]都存在 
    for (int i = 1; i <= q; i++) {
        int c;
        cin >> c;
        for (int j = 1; j <= c; j++) {
            int x;
            cin >> x;
            tms[x].push_back(i);
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < tms[i].size(); j++) { //取出第i条边最后一个存在区间，被第tms[i][j]个询问切成两个存在区间
            //注意此时tms[i]已经排好序才能这么干 
            pair<int, int> tmp = rg[i].back();
            rg[i].pop_back();
            if (tms[i][j] - 1 >= tmp.first)
                rg[i].push_back(make_pair(tmp.first, tms[i][j] - 1));
            if (tms[i][j] + 1 <= tmp.second)
                rg[i].push_back(make_pair(tms[i][j] + 1, tmp.second));
        }
        for (int j = 0; j < rg[i].size(); j++) {
            mdf(1, 1, q + 1, rg[i][j].first, rg[i][j].second + 1, make_pair(e[i].first, e[i].second)); //打标记 
        }
    }

    init(); //不要忘记初始化！QwQ
    dfs(1, 1, q + 1);
    for (int i = 1; i <= q; i++)
        if (ans[i])
            cout << "Connected" << endl;
        else
            cout << "Disconnected" << endl;
    return 0;
}