[BZOJ 4025]二分图
只会做水题力……qwq（搞错大小写，自裁请）
每条边存在的时间事一个区间，因此考虑线段树分治……首先当然要写一个可撤销并查集。
然后每个点维护他到父亲的边的边权膜2，合并啥的和食物链就很类似力……然后判定已联通两点间边数的奇偶性就直接把两个点到根的值加起来就行了，因为LCA到根的部分会算两遍，对答案无影响。
代码：
/**************************************************************
Problem: 4025
User: danihao123
Language: C++
Result: Accepted
Time:9928 ms
Memory:34840 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
const int maxn = 100005;
const int maxno = maxn << 2;
const int maxm = 200005;
int n, m, T;
int p[maxn], siz[maxn], d[maxn];
void init_dsu() {
for(int i = 1; i <= n; i ++) {
p[i] = i; siz[i] = 1; d[i] = 0;
}
}
int get_fa(int x) {
if(p[x] == x) {
return x;
} else {
return get_fa(p[x]);
}
}
int get_d(int x) {
if(p[x] == x) {
return 0;
} else {
return (d[x] + get_d(p[x])) % 2;
}
}
typedef std::pair<int, int> upd;
upd link_set(int x, int y, int v) {
if(siz[x] > siz[y]) std::swap(x, y);
p[x] = y; siz[y] += siz[x]; d[x] = v;
return std::make_pair(x, y);
}
upd merge_set(int x, int y) {
int v = (get_d(x) + get_d(y) + 1) % 2;
return link_set(get_fa(x), get_fa(y), v);
}
void unlink_set(const upd &pr) {
int x = pr.first, y = pr.second;
p[x] = x; siz[y] -= siz[x]; d[x] = 0;
}
bool is_same(int x, int y) {
return (get_fa(x) == get_fa(y));
}
std::vector<upd> event[maxno];
std::stack<std::pair<int, upd> > S;
void update(int o, int L, int R, int ql, int qr, upd v) {
if(ql <= L && R <= qr) {
event[o].push_back(v);
} else {
int M = (L + R) / 2;
if(ql <= M) update(o << 1, L, M, ql, qr, v);
if(qr > M) update(o << 1 | 1, M + 1, R, ql, qr, v);
}
}
int val[maxno];
void solve(int o, int L, int R) {
for(int i = 0; i < event[o].size(); i ++) {
const upd &pr = event[o][i];
int x = pr.first, y = pr.second;
if(is_same(x, y)) {
if((get_d(x) + get_d(y)) % 2 == 0) {
val[o] = 0;
break;
}
} else {
S.push(std::make_pair(o, merge_set(x, y)));
}
}
if(L == R) {
if(val[o] != 0) val[o] = 1;
} else {
if(val[o] != 0) {
int M = (L + R) / 2;
solve(o << 1, L, M);
solve(o << 1 | 1, M + 1, R);
}
}
while((!S.empty()) && S.top().first >= o) {
upd v = S.top().second; S.pop();
unlink_set(v);
}
}
void print(int o, int L, int R) {
if(L == R) {
if(val[o]) {
puts("Yes");
} else {
puts("No");
}
} else {
if(val[o] != -1) {
val[o << 1] = val[o];
val[o << 1 | 1] = val[o];
}
int M = (L + R) / 2;
print(o << 1, L, M);
print(o << 1 | 1, M + 1, R);
}
}
int main() {
memset(val, -1, sizeof(val));
scanf("%d%d%d", &n, &m, &T);
for(int i = 1; i <= m; i ++) {
int u, v, s, t; scanf("%d%d%d%d", &u, &v, &s, &t);
s ++; if(s <= t) update(1, 1, T, s, t, std::make_pair(u, v));
}
init_dsu(); solve(1, 1, T); print(1, 1, T);
return 0;
}
[LibreOJ 121]可离线动态图连通性
LCT+扫描线应该随便做吧这题……但我学了一下线段树分治
这个问题有删除非常的恶心，让我们考虑怎么去掉删除的影响。
每条边存在的时间段是一个区间，而区间在线段树上可以被表示为\(O(\log n)\)个区间。然后我们以时间为下标，对所有询问建线段树，然后对一段区间加边就是一个区间打标记，最后扫一遍线段树就可以解决问题。
同时需要注意，这个题在DFS线段树的过程中，往父亲回溯的时候是需要撤销之前的操作的。这样的话我们的并查集就不能使用路径压缩，但是可以按轶合并。
代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <map>
const int maxn = 5005;
const int maxm = 500005;
using pii = std::pair<int, int>;
struct Node {
Node *fa; int siz;
Node() {
fa = NULL; siz = 1;
}
void sc(Node *c) {
siz += c -> siz;
c -> fa = this;
}
void brk() {
fa -> siz -= siz;
fa = NULL;
}
};
Node *r[maxn];
int n;
void init_set() {
for(int i = 1; i <= n; i ++) {
r[i] = new Node();
}
}
Node *get_fa(Node *x) {
if(x -> fa == NULL) {
return x;
} else {
return get_fa(x -> fa);
}
}
Node *link_set(Node *x, Node *y) {
if(x -> siz < y -> siz) std::swap(x, y);
x -> sc(y); return y;
}
Node *merge_set(Node *x, Node *y) {
return link_set(get_fa(x), get_fa(y));
}
bool is_same(Node *x, Node *y) {
return (get_fa(x) == get_fa(y));
}
const int maxno = maxm << 2;
std::vector<pii> event[maxno];
void add_event(int o, int L, int R, int ql, int qr, const pii &e) {
if(ql <= L && R <= qr) {
event[o].push_back(e);
} else {
int M = (L + R) / 2;
if(ql <= M) add_event(o << 1, L, M, ql, qr, e);
if(qr > M) add_event(o << 1 | 1, M + 1, R, ql, qr, e);
}
}
pii que[maxno];
void add_query(int o, int L, int R, int p, const pii &e) {
if(L == R) {
que[o] = e;
} else {
int M = (L + R) / 2;
if(p <= M) {
add_query(o << 1, L, M, p, e);
} else {
add_query(o << 1 | 1, M + 1, R, p, e);
}
}
}
int ret[maxno];
std::stack<std::pair<Node*, int> > S;
void solve(int o, int L, int R) {
for(auto e : event[o]) {
int u = e.first, v = e.second;
if(!is_same(r[u], r[v])) {
#ifdef LOCAL
printf("Merging %d and %d.\n", u, v);
#endif
S.push(std::make_pair(merge_set(r[u], r[v]), o));
}
}
if(L == R) {
int u = que[o].first, v = que[o].second;
if(u == -1 && v == -1) {
ret[L] = -1;
} else {
if(is_same(r[u], r[v])) {
ret[L] = 1;
} else {
ret[L] = 0;
}
}
} else {
int M = (L + R) / 2;
solve(o << 1, L, M); solve(o << 1 | 1, M + 1, R);
}
while(!S.empty() && S.top().second >= o) {
Node *u = S.top().first; S.pop();
u -> brk();
}
}
std::map<pii, std::stack<int> > ma;
std::vector<pii> V;
int main() {
int m; scanf("%d%d", &n, &m);
init_set();
pii fl(-1, -1);
for(int i = 1; i <= m; i ++) {
pii e; int op;
scanf("%d%d%d", &op, &e.first, &e.second);
if(e.first > e.second) {
std::swap(e.first, e.second);
}
if(op == 2) {
add_query(1, 1, m, i, e);
} else {
add_query(1, 1, m, i, fl);
V.push_back(e);
if(op == 0) {
ma[e].push(i);
} else {
int last = ma[e].top(); ma[e].pop();
add_event(1, 1, m, last, i - 1, e);
}
}
}
for(auto e : V) {
while(!ma[e].empty()) {
int g = ma[e].top(); ma[e].pop();
add_event(1, 1, m, g, m, e);
}
}
solve(1, 1, m);
for(int i = 1; i <= m; i ++) {
if(ret[i] != -1) {
if(ret[i]) {
puts("Y");
} else {
puts("N");
}
}
}
return 0;
}
