CF576E Painting Edges

发表于 | 阅读数

每次为边染色，求是否可以染色（保证每个颜色组成的图是二分图）

（不能染色就跳过），$q$个操作，询问是每个操作是否能进行。

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

建立$k$个并茶几即可。

  • 问题是每个操作的时间不一定是给定的。但是由于线段树分治可以先操作前面的区间，然后我们根据是否可以染色，来反应之后这个的操作是否要延续之前操作。
  • 根据以上我们把修改的区间改为$[pre[i]+1,i-1]$
代码 
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 5e5 + 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 << 1], d[N << 1];
    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 (xx == yy)
            return;
        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[51];
pii p[N];
struct node
{
    int id, k;
} q[N];
int mp[N];
vector<pii> e[N << 2];
int n, m, k;
int ans[N];
int pre[N];
void insert(int pos, int ql, int qr, int l, int r, pii o)
{
    if (ql <= l && r <= qr)
    {
        //cout << ql << " " << qr << " " << l << " " << r << endl;
        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)
{
    vector<int> o;
    for (int i = 1; i <= k; i++)
        o.push_back(d[i].s.size());

    for (pii i : e[pos])
    {

        int id = i.first;
        int k = q[i.second].k;
        //cout << id << endl;

        ;

        {
            //cout << pos << " " << l << ' ' << r << ' ' << p[id].first << " " << p[id].second << " " << k << endl;
            d[k].merge(p[id].first, p[id].second + n);
            d[k].merge(p[id].first + n, p[id].second);
        }
    }
    int mid = (l + r) >> 1;

    if (l == r)
    {
        int id = q[l].id;
        int k = q[l].k;
        if (d[k].find(p[id].first) == d[k].find(p[id].second))
        {
            ans[l] = 0;
            q[l].k = pre[id];
        }
        else
        {
            pre[id] = q[l].k;
            ans[l] = 1;
        }
        //cout << l << " " << k << " " << p[id].first << " " << p[id].second << "----" << ans[l] << endl;
    }
    else
        solve(pos << 1, l, mid), solve(pos << 1 | 1, mid + 1, r);

    for (int i = 1; i <= k; i++)
        d[i].ret(o[i - 1]);
}

int main()
{
    n = read(), m = read(), k = read();
    int Q = read();
    for (int i = 1; i <= k; i++)
        d[i].init(2 * n);
    for (int i = 1; i <= m; i++)
    {
        p[i].first = read(), p[i].second = read();
        mp[i] = Q + 1;
    }
    for (int i = 1; i <= Q; i++)
    {
        q[i].id = read(), q[i].k = read();
    }
    for (int i = Q; i; i--)
    {
        int id = q[i].id;
        if (i < mp[id] - 1)
        {
            insert(1, i + 1, mp[id] - 1, 1, Q, mk(q[i].id, i));
        }

        mp[id] = i;
    }
    solve(1, 1, Q);
    for (int i = 1; i <= Q; i++)
    {
        puts(ans[i] ? "YES" : "NO");
    }
}