求问cdq为什么wa
查看原帖
求问cdq为什么wa
362762
lzyzs楼主2024/7/16 16:44
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 10, MAXX = 2e9;
int n, m;
struct edge{
	int x, y, color;
}E[N];

int usd[N], TempB[N], ans[N], nowbq[N];

struct T {int id, x, y, v;};

struct Edge {
	int x, y, id, in_or_out, v;
	void print() {
//	return;
		printf("x:%d y:%d id:%d v:%d in_or_out:%d\n", x, y, id, v, in_or_out);
	}
};

bool cmp2 (Edge a, Edge b) {return a.v > b.v;}

bool cmp1 (Edge a, Edge b) {
	if (a.in_or_out) return 0;
	if (b.in_or_out) return 1;
	return a.v > b.v;
}

int fa[N];
int ffind(int u) {
	if (fa[u] == u) return u;
	return fa[u] = ffind(fa[u]);
}
bool check (int x, int y) {
	return ffind(x) == ffind(y);
}
void merge (int x, int y) {
	fa[x] = ffind(y);
} 
void clear (vector<Edge> A) {
	for (int i = 0; i < A.size(); i++) 
		fa[A[i].x] = A[i].x, fa[A[i].y] = A[i].y;
}

void out (vector<Edge> A) {
	printf("Graph:\n");
	for (int i = 0; i < A.size(); i++) 
		A[i].print();
	cout << '\n';
}

int cs;
vector<T> pos;

void cdq (int l, int r, vector<Edge> old_graph, int cnt) {
	int mid = ((l + r) >> 1), now = ++ cs;
	for (int i = l; i <= r; i++) usd[pos[i].id] = now;
	for (int i = 0; i < old_graph.size(); i++) 
		old_graph[i].in_or_out = (usd[old_graph[i].id] == now);
	
	if(l==r) {
		for (int i = 0; i < old_graph.size(); i++) 
			nowbq[old_graph[i].id] = old_graph[i].v, old_graph[i].in_or_out = 0;
		for (int i = l; i <= r; i++) nowbq[pos[i].id] = pos[i].v;
		for (int i = 0; i < old_graph.size(); i++) 
			old_graph[i].v = nowbq[old_graph[i].id];
//		out(old_graph);
	}
	
	sort(old_graph.begin(), old_graph.end(), cmp1);
	vector<Edge> new_graph;
		
	// 必不选标记 
	
	clear(old_graph);
	for (int i = 0; i < old_graph.size(); i++) {
		if (old_graph[i].in_or_out) {new_graph.push_back(old_graph[i]); continue;}
		if (check(old_graph[i].x, old_graph[i].y)) continue;
		merge (old_graph[i].x, old_graph[i].y); 
		new_graph.push_back(old_graph[i]);
	}
	
	// 必选标记
	
	sort(new_graph.begin(), new_graph.end(), cmp1);
	clear(new_graph);
	
	for (int i = 0; i < new_graph.size(); i++) {
		TempB[i] = 0;
		if (new_graph[i].in_or_out) {merge (new_graph[i].x, new_graph[i].y); continue;}
		if (check(new_graph[i].x, new_graph[i].y)) continue;
//		printf("%d %d\n", new_graph[i].x, new_graph[i].y);
//		new_graph[i].print();
		merge (new_graph[i].x, new_graph[i].y); 
		cnt += new_graph[i].v;
		TempB[i] = 1;
	}
	if (l == r) 
		return void(ans[l] = cnt);
	// 缩点缩边 
	clear(new_graph);
	for (int i = 0; i < new_graph.size(); i++) 
		if(TempB[i]) 
			merge (new_graph[i].x, new_graph[i].y);
			
	for (int i = 0; i < new_graph.size(); i++) {
		new_graph[i].x = ffind(new_graph[i].x);
		new_graph[i].y = ffind(new_graph[i].y);
		if (new_graph[i].x == new_graph[i].y) new_graph[i].v = -MAXX;
	}
	sort(new_graph.begin(), new_graph.end(), cmp2);
	for (int i = new_graph.size() - 1; i >= 0; i--) {
		if (new_graph[i].v == -MAXX) new_graph.pop_back();
		else break;
	}
	
//	cout << l << ' ' << r << '\n';
//	printf("l:%d r:%d cnt:%d\n", l + 1, r + 1, cnt);
//	out(new_graph);
	
	cdq(l, mid, new_graph, cnt);
	for (int i = 0; i < new_graph.size(); i++) 
		nowbq[new_graph[i].id] = new_graph[i].v;
	for (int i = l; i <= mid; i++) nowbq[pos[i].id] = pos[i].v;
	for (int i = 0; i < new_graph.size(); i++) 
		new_graph[i].v = nowbq[new_graph[i].id];
//	out(new_graph);
	cdq(mid + 1, r, new_graph, cnt);
}
int deg[N], cnt, nd, js;
signed main () {
//	freopen("T.txt", "r", stdin);
	vector<Edge> graph;
	scanf("%d%d", &n, &m);
	pos.push_back(T{0, 0, 0, 0});
	for (int i = 1; i <= m; i++) {
		int x, y, color;
		scanf("%d%d%d", &x, &y, &color);
		E[i] = edge{x, y, color};	
		if (color) {
			nd += (deg[E[i].x] == 0) + (deg[E[i].y] == 0);
			deg[E[i].x] ++, deg[E[i].y] ++;
			js += -2 + 2 * ((deg[E[i].x] & 1) + (deg[E[i].y] & 1));
		}
		graph.push_back(Edge{x, y, i, 0, color});
	}
	int q, opt, t;
	scanf("%d", &q);
	vector<pair<int, int> > np;
	for (int i = 1; i <= q; i++) {
		scanf("%d", &opt);
		if (opt == 1) {
			scanf("%d", &t); t++;
			E[t].color = !E[t].color;
			if(E[t].color == 0) {
				deg[E[t].x] --, deg[E[t].y] --;
				nd -= (deg[E[t].x] == 0) + (deg[E[t].y] == 0);
			} else {
				nd += (deg[E[t].x] == 0) + (deg[E[t].y] == 0);
				deg[E[t].x] ++, deg[E[t].y] ++;
			}
			js += -2 + 2 * ((deg[E[t].x] & 1) + (deg[E[t].y] & 1));
			pos.push_back(T{t, E[t].x, E[t].y, E[t].color});
			cnt ++;
		} else {
			np.push_back(pair<int, int>{cnt, js ? -MAXX : nd});
		}
	}
	cdq(0, pos.size() - 1, graph, 0);
	for(int i = 0; i < np.size(); i++) 
		printf("%d\n", (np[i].second - ans[np[i].first] >= 0) ? np[i].second - ans[np[i].first] : -1);
	
	return 0;
}
2024/7/16 16:44
加载中...