P5787 二分图 /【模板】线段树分治

发表于 | 阅读数

线段树分治。

支持删边，加边。询问是否为二分图

以时间为区间，这样就不用单独时间更新边，而是根据线段树的递归来拓展边。

判断二分图用扩展并茶几，由于并茶几无法整体带入，需要撤销，这里需要用到撤销并茶几

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 4e5 + 10;
const int mod = 1e9 + 7;

int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}

struct Dsu
{
    int fa[N], d[N];
    struct Tmp
    {
        int x, y, add;
    };
    stack<Tmp> s;
    int find(int x)
    {
        while (x != fa[x])
            x = fa[x];
        return x;
    }
    void init(int n)
    {
        while (!s.empty())
            s.pop();
        for (int i = 1; i <= n; i++)
            fa[i] = i, d[i] = 0;
    }
    void merge(int x, int y)
    {
        int xx = find(x);
        int yy = find(y);
        if (d[xx] > d[yy])
            swap(xx, yy);
        s.push((Tmp){xx, yy, d[xx] == d[yy]});
        fa[xx] = yy;
        d[yy] += (d[xx] == d[yy]);
    }
    void ret(int o)
    {
        while (s.size() > o)
        {
            Tmp x = s.top();
            fa[x.x] = x.x;
            d[x.y] -= x.add;
            s.pop();
        }
    }
} d;
vector<pii> e[N << 2];
int n, m, k;
int ans[N];
void insert(int pos, int ql, int qr, int l, int r, pii o)
{
    if (ql <= l && r <= qr)
    {
        e[pos].push_back(o);
        return;
    }
    int mid = (l + r) >> 1;
    if (ql <= mid)
        insert(pos << 1, ql, qr, l, mid, o);
    if (qr > mid)
        insert(pos << 1 | 1, ql, qr, mid + 1, r, o);
}

void solve(int pos, int l, int r)
{
    int o = d.s.size();
    bool flag = 1;

    for (pii i : e[pos])
    {
        int x = d.find(i.first);
        int y = d.find(i.second);
        if (x == y)
        {
            for (int i = l; i <= r; i++)
                ans[i] = 0;
            flag = 0;
            break;
        }
        d.merge(i.first, i.second + n);
        d.merge(i.first + n, i.second);
    }
    int mid = (l + r) >> 1;
    if (flag)
    {
        if (l == r)
            return;
        solve(pos << 1, l, mid), solve(pos << 1 | 1, mid + 1, r);
    }

    d.ret(o);
}

int main()
{
    n = read(), m = read(), k = read();
    d.init(2 * n);
    for (int i = 1; i <= k; i++)
        ans[i] = 1;
    for (int i = 1; i <= m; i++)
    {
        int u = read(), v = read(), l = read(), r = read();
        insert(1, l + 1, r, 1, k, mk(u, v));
    }

    solve(1, 1, k);
    for (int i = 1; i <= k; i++)
    {
        puts(ans[i] ? "Yes" : "No");
    }
}