洛谷 P2147 [SDOI2008]洞穴勘测 (线段树分治)

题目链接

题解

早就想写线段树分治的题了。

对于每条边，它存在于一段时间

我们按时间来搞

我们可把一条边看做一条线段

我们可以模拟线段树操作，不断分治下去

把覆盖\(l-r\)这段时间的线段筛选出来,用并查集维护联通性，回溯时撤销操作

注意不能使用路径压缩（不能破坏树的结构，方便撤销操作）

Code

#include<bits/stdc++.h>

#define LL long long

#define RG register

using namespace std;

inline int gi() {

    int f = 1, s = 0;

    char c = getchar();

    while (c != '-' && (c < '0' || c > '9')) c = getchar();

    if (c == '-') f = -1, c = getchar();

    while (c >= '0' && c <= '9') s = s*10+c-'0', c = getchar();

    return f == 1 ? s : -s;

}

const int N = 10010, M = 200010;

struct question {

    int time, u, v;

}q[M];

int ql, w;

struct bian {

    int u, v, s, e;

};

vector<bian> g;

map<pair<int, int>, int> Mp;

int siz[N], fa[N];

inline int find(int x) {

    return x == fa[x] ? x : find(fa[x]);

}

pair<int, int> stk[M];

int top;

void link(int x, int y) {//按秩合并

    x = find(x); y = find(y);

    if (x == y) {

        stk[++top] = make_pair(0, 0);

        return ;

    }

    if (siz[x] < siz[y]) swap(x, y);

    stk[++top] = make_pair(x, y);//y接在x上

    fa[y] = x;

    siz[x] += siz[y];

    return ;

}

void clear() {//撤销操作

    int x = stk[top].first, y = stk[top--].second;

    if (!x && !y) return ;

    fa[y] = y;

    siz[x] -= siz[y];

    return ;

}

void divide(int l, int r, vector<bian> E) {

    vector<bian> L, R;

    int tmp = top, mid = (l + r) >> 1;

    for (int i = 0; i < (int)E.size(); i++) {

        if (E[i].s <= l && E[i].e >= r) link(E[i].u, E[i].v);

        else {

            if (E[i].s <= mid) L.push_back(E[i]);

            if (E[i].e > mid) R.push_back(E[i]);

        }

    }

    if (l == r) {

        while (q[w].time == l && w <= ql) {

            if (find(q[w].u) == find(q[w].v)) printf("Yes\n");

            else printf("No\n");

            w++;

        }

        if (w > ql) exit(0);

        return ;

    }

    else divide(l, mid, L), divide(mid+1, r, R);

    while (top > tmp) clear();

    return ;

}

int main() {

    int n = gi(), m = gi(), x, y;

    char s[10];

    for (int i = 1; i <= m; i++) {

        cin >> s >> x >> y;

        if (x > y) swap(x, y);

        if (s[0] == 'C') {

            if (Mp.find(make_pair(x, y)) == Mp.end())

                g.push_back((bian){x, y, i, m}), Mp[make_pair(x, y)] = g.size()-1;

        }

        else if (s[0] == 'D') {

            g[Mp[make_pair(x, y)]].e = i-1;

            Mp.erase(Mp.find(make_pair(x, y)));

        }

        else q[++ql] = (question) {i, x, y};

    }

    /*for (int i = 0; i < g.size(); i++)

        printf("%d %d %d %d\n", g[i].u, g[i].v, g[i].s, g[i].e);*/

    w = 1;

    for (int i = 1; i <= n; i++) fa[i] = i, siz[i] = 1;

    divide(1, m, g);

    return 0;

}

巴特西

洛谷 P2147 [SDOI2008]洞穴勘测 (线段树分治)

题目链接

题解

Code

最新文章

热门文章