【BZOJ 4530】[BJOI2014] 大融合

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4530

解题报告

这题LCT是可以做的

但因为本题没有要求强制在线
所以我们可以用并查集来维护连通性,再用线段树合并来支持支持DFS序的区间询问
总的时间复杂度:$O(n \log n)$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200009; 
const int M = N * 21;

int n, m, vis[N], head[N], nxt[N], to[N];
int dep[N], beg[N], out[N], sz[N], fa[N];
struct Data{
	int t, x, y;
	inline Data() {
	}
	inline Data(bool a, int b, int c):t(a), x(b), y(c) {
	} 
}opt[N];

inline int read() {
	char c = getchar(); int ret = 0, f = 1;
	for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
	for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
	return ret * f;
}

inline void AddEdge(int u, int v) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

inline void DFS(int w, int f) {
	static int D = 0;
	vis[w] = 1;
	beg[w] = ++D;
	dep[w] = dep[f] + 1;
	for (int i = head[w]; i; i = nxt[i]) {
		if (to[i] != f) {
			DFS(to[i], w);
		}
	}
	out[w] = D;
}

inline int find(int x) {
	return fa[x] == x? x: fa[x] = find(fa[x]);
}

class SegmentTree{
int cnt, ch[M][2], sum[M], root[N];
public:
	inline void insert(int p, int v) {
		insert(root[p], 1, n, v);
	}
	inline void merge(int a, int b) {
		root[a] = Merge(root[a], root[b]);
	}
	inline int query(int p, int l, int r) {
		return query(root[p], 1, n, l, r);
	}
private:
	inline int Merge(int a, int b) {
		if (!a || !b) {
			return a + b;
		} else {
			sum[a] += sum[b];
			ch[a][0] = Merge(ch[a][0], ch[b][0]);
			ch[a][1] = Merge(ch[a][1], ch[b][1]);
			return a;
		}
	}
	inline void insert(int &w, int l, int r, int p) {
		sum[w = ++cnt] = 1;
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (p < mid) {
				insert(ch[w][0], l, mid - 1, p);
			} else {
				insert(ch[w][1], mid, r, p);
			}
		}
	} 
	inline int query(int w, int l, int r, int L, int R) {
		if (!w) {
			return 0;
		} else if (L <= l && r <= R) {
			return sum[w];
		} else {
			int mid = l + r + 1 >> 1, ret = 0;
			ret += L < mid? query(ch[w][0], l, mid - 1, L, R): 0;
			ret += mid <= R? query(ch[w][1], mid, r, L, R): 0;
			return ret;
		}
	}
}SGT;

int main() {
	n = read(); m = read();
	for (int i = 1; i <= m; i++) {
		char cmd[3]; 
		scanf("%s", cmd);
		int u = read(), v = read();
		if (cmd[0] == 'A') {
			AddEdge(u, v);
		}
		opt[i] = Data(cmd[0] == 'A', u, v);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			DFS(i, i);
		}
	}
	for (int i = 1; i <= n; i++) {
		sz[i] = 1;
		fa[i] = i;
		SGT.insert(i, beg[i]);
	}
	for (int i = 1; i <= m; i++) {
		int u = opt[i].x, v = opt[i].y;
		if (opt[i].t == 1) {
			SGT.merge(find(u), find(v));
			sz[find(u)] += sz[find(v)];
			fa[find(v)] = find(u);
		} else {
			if (dep[u] < dep[v]) {
				swap(u, v);
			}
			int p1 = SGT.query(find(u), beg[u], out[u]);
			int p2 = sz[find(u)] - p1;
			printf("%lld\n", (LL)p1 * p2);
		}
	}
	return 0;
}

40 thoughts to “【BZOJ 4530】[BJOI2014] 大融合”

  1. 203946 533355Hey. Extremely nice web web site!! Man .. Excellent .. Wonderful .. Ill bookmark this web site and take the feeds alsoI am pleased to locate so a lot valuable data here within the article. Thanks for sharing 425447

  2. 191786 766774It was any exhilaration discovering your website yesterday. I arrived here nowadays hunting new points. I was not necessarily frustrated. Your suggestions after new approaches on this thing have been beneficial plus an superb assistance to personally. We appreciate you leaving out time to write out these items and then for revealing your thoughts. 419478

  3. 941669 239038Found your weblog and decided to have a study on it, not what I typically do, but this blog is wonderful. Awesome to see a web site thats not spammed, and in fact makes some sense. Anyway, wonderful write up. 783382

  4. 197729 289549There exist a couple of many different distinct levels among the California Weight loss program and each and every a person is pretty important. You are procedure stands out as the the actual giving up with all the power. weight loss 788521

  5. After exploring a few of the articles on your web site, I truly appreciate your
    way of blogging. I book marked it to my bookmark webpage list
    and will be checking back in the near future.
    Please visit my website as well and let me know your opinion.

  6. Simply want to say your article is as surprising.

    The clarity in your post is simply excellent
    and i could assume you are an expert on this subject.

    Well with your permission let me to grab your feed to keep up to date with forthcoming post.
    Thanks a million and please carry on the gratifying work.

  7. Thanks for the good writeup. It in fact was a entertainment account
    it. Glance advanced to far delivered agreeable from you!
    However, how could we keep in touch?

  8. My developer is trying to persuade me to move
    to .net from PHP. I have always disliked the idea because of
    the expenses. But he’s tryiong none the less. I’ve been using WordPress on numerous websites
    for about a year and am worried about switching to another platform.

    I have heard fantastic things about blogengine.net.
    Is there a way I can import all my wordpress content into it?
    Any help would be really appreciated!

  9. Hey There. I found your weblog the usage of msn. That is an extremely well written article.

    I will be sure to bookmark it and come back
    to read extra of your useful information. Thanks for the post.
    I’ll definitely comeback.

  10. After exploring a handful of the blog articles on your web site, I really appreciate your technique
    of writing a blog. I added it to my bookmark webpage list and will be checking
    back in the near future. Please visit my website as
    well and tell me what you think.

  11. It is appropriate time to make some plans for the future and it’s time to be happy. I’ve read this post and if I could I desire to suggest you some interesting things or tips. Maybe you can write next articles referring to this article. I want to read more things about it!

  12. Hello! Quick question that’s totally off topic. Do you know how
    to make your site mobile friendly? My web site looks weird when browsing from my iphone4.

    I’m trying to find a theme or plugin that might be able to
    fix this issue. If you have any suggestions, please share.
    Thank you!

  13. It’s a shame you don’t have a donate button! I’d certainly donate to this
    outstanding blog! I guess for now i’ll settle for bookmarking and adding your
    RSS feed to my Google account. I look forward to fresh updates and will talk about this
    blog with my Facebook group. Chat soon!

  14. I am not sure where you are getting your info, but good topic.
    I needs to spend some time learning much more or understanding more.
    Thanks for great information I was looking for this information for my mission.

  15. Hello! Someone in my Myspace group shared this site with us so I came to
    check it out. I’m definitely loving the information. I’m bookmarking and will be tweeting this
    to my followers! Superb blog and superb style and design.

  16. Someone essentially help to make seriously articles I would state. This is the very first time I frequented your website page and thus far? I amazed with the research you made to make this particular publish extraordinary. Excellent job!

Leave a Reply to sling tv Cancel reply

Your email address will not be published. Required fields are marked *