【日常小测】友好城市

相关链接

题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:http://oi.cyo.ng/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题的前置知识是把求$SCC$优化到$O(\frac{n^2}{32})$
具体来说,就是使用$bitset$配合$Kosaraju$算法

有了这个技能以后,我们配合$ST$表来实现提取一个区间的边的操作
这样的话,总的时间复杂度是:$O(\frac{(\sqrt{m} \log m + q) n^2}{32}+q \sqrt{m})$

然后我懒,没有用$ST$表,用的莫队,时间复杂度是$O(\frac{(m + q) n^2}{32}+q \sqrt{m})$
调一调块大小,勉勉强强卡过去了

Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int 
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ]; 
struct Query{
	int l, r, blk, id;
	inline bool operator < (const Query &Q) const {
		return blk < Q.blk || (blk == Q.blk && r < Q.r);
	}
}qy[QQ];
struct Bitset{
	UI v[5];
	inline void flip(int x) {
		v[x >> 5] ^= 1 << (x & 31);
	}
	inline void set(int x) {
		v[x >> 5] |= 1 << (x & 31);
	}
	inline void reset() {
		memset(v, 0, sizeof(v));
	}
	inline bool operator [](int x) {
		return v[x >> 5] & (1 << (x & 31));
	}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

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

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
 	a1[u].set(v);
 	a2[v].set(u);
}

class Kosaraju{
	vector<int> que;
	Bitset vis;
public:
	inline int solve() {
		vis.reset();
		que.clear();
		for (int i = 1; i <= n; ++i) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.reset();
		int ret = 0;
		for (int j = n - 1; ~j; j--) {
			int i = que[j];
			if (!vis[i]) {
				int cnt = dfs1(i);
				ret += cnt * (cnt - 1) / 2;
			}
		}
		return ret;
	}
private:
	inline void dfs0(int w) {
		vis.flip(w);
		for (int i = 0; i < 5; i++) {
			for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					dfs0(t);
				}
			}
		}
		que.push_back(w);
	}
	inline int dfs1(int w) {
		vis.flip(w);
		int ret = 1;
		for (int i = 0; i < 5; i++) {
			for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					ret += dfs1(t);
				}
			}
		}
		return ret;
	}
}scc;

int main() {
	freopen("friend.in", "r", stdin);
	freopen("friend.out", "w", stdout);
	n = read(); m = read(); q = read();
	for (int i = 1; i <= m; i++) {
		U[i] = read();
		V[i] = read();
		AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
	}
	for (int i = 1; i <= q; i++) {
		qy[i].l = read(); 
		qy[i].r = read();
		qy[i].blk = qy[i].l / BlockSize;
		qy[i].id = i;
	}
	sort(qy + 1, qy + 1 + q);
	Bitset CurG[N], CurRG[N];
	for (int i = 1, L = 1, R = 0; i <= q; i++) {
		if (qy[i].blk != qy[i - 1].blk || i == 1) {
			L = qy[i].blk + 1;
			R = L - 1;	
			for (int j = 1; j <= n; j++) {
				CurG[j].reset();
				CurRG[j].reset();
			}
		}
		if (qy[i].r / BlockSize - 1 > R) {
			for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
				for (int k = 1; k <= n; k++) {
					for (int h = 0; h < 5; h++) {
						CurG[k].v[h] ^= PreG[j][k].v[h];
						CurRG[k].v[h] ^= PreRG[j][k].v[h];
					}
				}
			}
			R = qy[i].r / BlockSize - 1;
		}
		if (L <= R) {
			for (int i = 1; i <= n; i++) {
				g[i] = CurG[i];
				rg[i] = CurRG[i];
			}
			for (int l = qy[i].l; l < L * BlockSize; l++) {
				AddEdge(U[l], V[l], g, rg);
			}
			for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
				AddEdge(U[r], V[r], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		} else {
			for (int i = 1; i <= n; i++) {
				g[i].reset();
				rg[i].reset();
			}
			for (int j = qy[i].l; j <= qy[i].r; ++j) {
				AddEdge(U[j], V[j], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		}
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

78 thoughts to “【日常小测】友好城市”

  1. I have been exploring for a bit for any high quality articles
    or weblog posts on this sort of house . Exploring in Yahoo
    I at last stumbled upon this web site. Reading this information So i am satisfied to convey that
    I’ve a very excellent uncanny feeling I found out exactly what I needed.
    I most definitely will make sure to don?t overlook this site and give it a look regularly.

  2. hey there and thank you for your information – I have
    definitely picked up something new from right here.
    I did however expertise some technical issues using this web site, as I experienced to reload the web
    site a lot of times previous to I could get it to load properly.
    I had been wondering if your hosting is OK? Not that I am complaining, but slow loading instances
    times will sometimes affect your placement in google and could damage your high quality
    score if advertising and marketing with Adwords. Anyway I am
    adding this RSS to my email and can look out for a lot more of your respective exciting content.
    Ensure that you update this again soon.

  3. I was recommended this web site by my cousin. I am now not sure whether this put up is written through him as nobody else know such
    special about my difficulty. You are wonderful!
    Thanks!

  4. Write more, thats all I have to say. Literally, it
    seems as though you relied on the video to make your point.
    You definitely know what youre talking about, why waste your
    intelligence on just posting videos to your weblog when you could be giving
    us something enlightening to read?

  5. I’m not sure why but this web site is loading extremely slow for me.
    Is anyone else having this problem or is it a problem on my end?
    I’ll check back later on and see if the problem
    still exists.

  6. Today, I went to the beachfront with my children. I found a sea shell and gave it to
    my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She placed the shell to her ear and screamed.

    There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this is totally off topic but I had
    to tell someone!

  7. Nice blog here! Additionally your web site loads up fast!

    What web host are you the usage of? Can I am getting your associate link
    for your host? I wish my website loaded up
    as fast as yours lol natalielise pof

  8. I believe this is among the such a lot vital information for me.

    And i’m satisfied reading your article. But should observation on some common things, The site style is perfect, the articles is truly great :
    D. Good activity, cheers

  9. Hello there, just became alert to your blog through Google, and found that it’s truly informative.
    I’m going to watch out for brussels. I’ll appreciate if you continue
    this in future. Lots of people will be benefited from
    your writing. Cheers!

  10. With havin so much content do you ever run into any issues of plagorism or
    copyright violation? My site has a lot of unique content
    I’ve either created myself or outsourced but it looks like a lot of it is popping it up all over the web without my authorization. Do you
    know any ways to help stop content from being ripped off?
    I’d definitely appreciate it.

  11. An interesting discussion is worth comment. I do think that you need to
    write more about this subject matter, it may not be a taboo subject but typically folks don’t talk about these issues.
    To the next! Many thanks!!

  12. This is really interesting, You are a very skilled blogger.
    I have joined your rss feed and look forward to seeking more of your great post.
    Also, I’ve shared your web site in my social networks!

  13. It’s in reality a nice and helpful piece of information. I’m happy
    that you simply shared this helpful information with us.
    Please stay us informed like this. Thanks for sharing.

  14. I simply could not leave your site before suggesting that I really loved the
    standard information a person provide on your visitors?
    Is going to be again frequently to inspect new posts

  15. Excellent post. Keep posting such kind of information on your
    blog. Im really impressed by your site.
    Hi there, You’ve done an excellent job. I will certainly digg
    it and for my part suggest to my friends. I’m sure
    they’ll be benefited from this site.

  16. Excellent post. I used to be checking constantly this weblog and I am impressed!
    Extremely useful info specially the closing section :
    ) I deal with such info a lot. I was looking for this particular
    information for a very lengthy time. Thank you and
    best of luck.

  17. You are so interesting! I do not think I have
    read through anything like that before. So nice to discover
    somebody with a few unique thoughts on this subject. Really..
    many thanks for starting this up. This website is one thing that is required on the web, someone with some originality!

  18. Unquestionably believe that which you said. Your favorite justification appeared to be on the net
    the simplest thing to be aware of. I say to you, I definitely
    get irked while people consider worries that they just do not know about.
    You managed to hit the nail upon the top as well as defined out the
    whole thing without having side-effects , people could take a signal.
    Will likely be back to get more. Thanks

  19. Wonderful beat ! I wish to apprentice even as you amend your
    site, how can i subscribe for a weblog site? The account aided me a acceptable deal.

    I were a little bit acquainted of this your broadcast offered bright clear idea

  20. Hello would you mind stating which blog platform you’re using?
    I’m planning to start my own blog in the near future but I’m having a hard time choosing between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your layout seems different then most blogs and
    I’m looking for something unique. P.S Sorry for getting off-topic but I had to ask!

  21. I loved as much as you will receive carried out right here.
    The sketch is tasteful, your authored subject matter stylish.
    nonetheless, you command get bought an impatience over that you wish be delivering the following.
    unwell unquestionably come more formerly again as exactly the same nearly a
    lot often inside case you shield this hike.

  22. whoah this blog is wonderful i love reading your posts.

    Keep up the great work! You know, many people are hunting around for this info, you could aid them greatly.

  23. I don’t even know how I ended up here, but I thought this post was
    great. I don’t know who you are but certainly you are going to a famous blogger if you are not already 😉
    Cheers!

  24. First of all I want to say superb blog! I had a quick question in which I’d like to
    ask if you don’t mind. I was curious to know how you center yourself
    and clear your thoughts prior to writing. I’ve had difficulty clearing my
    mind in getting my thoughts out there. I do take pleasure in writing but
    it just seems like the first 10 to 15 minutes are lost simply just trying to figure out
    how to begin. Any ideas or tips? Many thanks!

  25. I’m not sure exactly why but this site is loading incredibly slow for me.

    Is anyone else having this issue or is it a issue on my end?
    I’ll check back later on and see if the problem still exists.

  26. Howdy very nice blog!! Guy .. Beautiful .. Superb .. I’ll bookmark your
    web site and take the feeds also? I am glad to find
    a lot of helpful information right here in the submit, we
    need develop more techniques in this regard, thank you for
    sharing. . . . . .

  27. You really make it appear really easy with your presentation however I find this matter to be actually something which I believe I might by no means understand. It seems too complex and extremely large for me. I am having a look ahead on your subsequent post, I will attempt to get the cling of it!

  28. Hey there! This post could not be written any better!
    Reading through this post reminds me of my good old room mate!

    He always kept chatting about this. I will forward this
    article to him. Pretty sure he will have a good read. Thanks for sharing!

  29. Does your website have a contact page? I’m having trouble locating it but,
    I’d like to send you an e-mail. I’ve got some suggestions for your blog
    you might be interested in hearing. Either way, great site and I look forward to seeing it improve over time.

  30. I’m not that much of a online reader to be honest but your sites really nice,
    keep it up! I’ll go ahead and bookmark your
    website to come back down the road. All the best

  31. Hi, Neat post. There is an issue with your site in web explorer, could test this… IE still is the marketplace chief and a good part of other people will leave out your wonderful writing because of this problem.

Leave a Reply to quest bars cheap Cancel reply

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