CF576E Painting Edges

IOI2020集训队作业

不是上午发的那货能叫博客吗?也太简单了吧

所以这里再补一篇....虽然考砸了但还是要学下去啊

给定一张 $n$ 个点 $m$ 条边的无向图。
一共有 $k$ 种颜色，一开始，每条边都没有颜色。
定义合法状态为仅保留染成 $k$ 种颜色中的任何一种颜色的边，图都是一张二分图。
有 $q$ 次操作，第 $i$ 次操作将第 $e_i$ 条边的颜色染成 $c_i$ 。
但并不是每次操作都会被执行，只有当执行后仍然合法，才会执行本次操作。
你需要判断每次操作是否会被执行。
$n,m,q \le 5 \times 10^5$ ， $k \le 50$ 。

其实第一眼就应该看出来是一道[模板]线段树分治啊

每条边可能出现可能消失,满足在时间轴上出现是一个区间
询问是否为二分图啊

这样的一看就是线段树分治

具体怎么做?

我们按照dfs序去遍历线段树

然后记录从当且叶子到根的每个点的f数组状态, $O(nlogn)$

在线段树上遇到一条边我们就加入这条边,从一个点离开时我们再把这个边的影响删掉

就是方便我们回溯

这样在叶子结点就是具体的每个时刻可以用来回答答案啦

请仔细研读代码

code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 7;
int n, m, k, q;
struct E {
	int u, v, c;
} e[MAXN];

struct P {
	int e, c;
} p[MAXN];

vector<int> chan[MAXN];
vector<int>::iterator pos[MAXN];

struct Dsuontree {
	int fa[MAXN];
	bool fw[MAXN];
	short h[MAXN];
	bool check(int id) {
		int u = e[id].u, v = e[id].v, w = 0;
		while(fa[u])w ^= fw[u], u = fa[u];
		while(fa[v])w ^= fw[v], v = fa[v];
		// w的奇偶性反应了,如果为偶数就存在奇环
		return u != v || w;//如果为奇数就没了啊!奇环...
	}
	E merge(int u, int v) {
		int w = 1;
		while(fa[u])w ^= fw[u], u = fa[u];
		while(fa[v])w ^= fw[v], v = fa[v];
		//我们得到u,v两个点的祖先以及异或和
		if(u == v)return (E) {
			0
		};//妈耶,和个毛
		h[u] > h[v] ? swap(u, v) : void(), fa[u] = v, fw[u] = w;//这个w是因为我们路径压缩之后的
		//按秩合并啊
		return (E) {
			u, v, (h[u] == h[v]) ? h[v]++ : h[v]
		};
		//如果相同我们秩加1
	}
} dsu[51];

struct seg {
	vector<E> t[4 * MAXN], rec[202];
	void ins(int k, int d) {
		rec[d].clear();
		for(int i = 0; i < t[k].size(); ++i) {
			rec[d].push_back(dsu[t[k][i].c].merge(t[k][i].u, t[k][i].v));
			//把k号节点记录的所有边添加进d号状态里面
		}
	}
	void del(int k, int d) {
		for(int i = t[k].size() - 1; i >= 0; --i) {
			if(!rec[d][i].u)continue;
			int u = rec[d][i].u, v = rec[d][i].v, c = t[k][i].c;
			dsu[c].fa[u] = dsu[c].fw[u] = 0;//直接清掉...因为我们一定merge的是树根
			dsu[c].h[v] = rec[d][i].c;//然后v直接恢复秩
		}
	}
	void modi(int l, int r, int k, int st, int en, E v) {
		if(st > r || en < l)return ;
		if(st <= l && en >= r)return t[k].push_back(v);//区间放线段
		int mid = l + r >> 1;
		modi(l, mid, k << 1, st, en, v);
		modi(mid + 1, r, k << 1 | 1, st, en, v);
	}
	void work(int l, int r, int k, int d) {
		ins(k, d);//插入线段
		if(l == r) {
			int id = p[l].e;
            //找到边
			++pos[id];
            //看看边该是哪个颜色了
			dsu[p[l].c].check(id) ? (puts("YES"), e[id].c = p[l].c) : (puts("NO"));//询问特定颜色中的情况,删边显然不会影响啊
			return modi(1, q, 1, l + 1, (*pos[id]) - 1, e[id]), del(k, d);
            //从l+1开始,这条边一直到*pos的时间,他都是这个颜色啊!
            //并且记得回溯时删除/kk
		}
		int mid = (l + r) >> 1;
		work(l, mid, k << 1, d + 1);
		work(mid + 1, r, k << 1 | 1, d + 1); //向左右子树递归啊,调用更多状态记录
		del(k, d);//回溯时删掉
	}
} seg;

int main() {
	scanf("%d%d%d%d", &n, &m, &k, &q);
	for(int i = 1; i <= m; ++i)scanf("%d%d", &e[i].u, &e[i].v);
	for(int i = 1; i <= q; ++i) {
		scanf("%d%d", &p[i].e, &p[i].c), chan[p[i].e].push_back(i);
        //每条边上放下这个改变时间
	}
	for(int i = 1; i <= m; ++i) {
		chan[i].push_back(q + 1), pos[i] = chan[i].begin();
        //每条边先初始化
	}
	seg.work(1, q, 1, 0);
	return 0;
}

~~zzz?~~

我也不想颓

夏晓光(loveJY)的博客

P3763 [TJOI2017]DNA