4025: 二分图

题意：加入边，删除边，查询当前图是否为二分图

本来想练lct，然后发现了线段树分治的做法，感觉好厉害。

lct做法的核心就是维护删除时间的最大生成树

首先口胡一个分块做法，和hnoi2016第一题类似的偏序关系，一样做。

线段树分治

数据结构题中如果使用对时间cdq分治，要求每个操作独立，不能很好的处理撤销(删除)操作。

采取线段树区间标记的思想

对于一个操作，它的存在时间是\([l,r]\)

我们模仿线段树打标记的过程进行分治，\(cdq(l,r,S)\)表示当前处理时间\([l,r]\)，操作集合为\(S\)

如果区间就是当前区间，那么进行操作

否则继续递归

对于本题，用启发式合并不路径压缩的并查集实现加边和撤销

越卡常越慢是smg

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long ll;

const int N=2e5+5;

inline int read(){

    char c=getchar(); int x=0,f=1;

    while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

    while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

    return x*f;

}

int n, m, T, u, v, l, r;

struct edge {

    int u, v, l, r;

    bool operator <(const edge &a) const {return l == a.l ? r < a.r : l < a.l;}

};

typedef vector<edge> meow;

meow a;

int top;

namespace ufs {

    struct node {int fa, val, size;} t[N];

    struct info {int x, y; node a, b;} st[N];

    inline void init() {for(int i=1; i<=n; i++) t[i] = (node){i, 0, 1};}

    inline int find(int x) {while(t[x].fa != x) x = t[x].fa; return x;}

    inline int dis(int x) {

        int ans=0;

        while(t[x].fa != x) ans ^= t[x].val, x = t[x].fa;

        return ans;

    }

    inline void link(int x, int y) {

        int val = dis(x) ^ dis(y) ^ 1;

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

        st[++top] = (info) {x, y, t[x], t[y]};

        if(t[x].size > t[y].size) swap(x, y);

        t[x].fa = y; t[x].val = val; t[y].size += t[x].size;

    }

    inline void recov(int bot) {

        while(top != bot) {

            info &now = st[top--];

            t[now.x] = now.a; t[now.y] = now.b;

        }

    }

} using namespace ufs;

void cdq(int l, int r, meow &a) {

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

    meow b, c;

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

        edge &now = a[i];

        int x = now.u, y = now.v;

        if(now.l == l && now.r == r) {

            int p = find(x), q = find(y);

            if(p == q) {

                int val = dis(x) ^ dis(y);

                if(val == 0) {

                    for(int i=l; i<=r; i++) puts("No");

                    recov(bot); return;

                }

            } else link(x, y);

        }

        else if(now.r <= mid) b.push_back(now);

        else if(mid < now.l) c.push_back(now);

        else b.push_back( (edge){now.u, now.v, now.l, mid} ), c.push_back( (edge){now.u, now.v, mid+1, now.r} );

    }

    if(l == r) puts("Yes");

    else cdq(l, mid, b), cdq(mid+1, r, c);

    recov(bot);

}

int main() {

    //freopen("in", "r", stdin);

    n=read(); m=read(); T=read();

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

        u=read(), v=read(), l=read()+1, r=read();

        if(l > r) continue;

        a.push_back((edge){u, v, l, r});

    }

    init();

    cdq(1, T, a);

}

巴特西

BZOJ 4025: 二分图 [线段树CDQ分治并查集]

4025: 二分图

线段树分治

最新文章

热门文章

巴特西

BZOJ 4025: 二分图 [线段树CDQ分治 并查集]

4025: 二分图

线段树分治

最新文章

热门文章

BZOJ 4025: 二分图 [线段树CDQ分治并查集]