相关链接
题目传送门: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; }
Keep on working, great job!
Greetings! Very useful advice within this article!
It is the little changes that will make the most significant changes.
Many thanks for sharing!
My family always say that I am wasting my time here at web, but
I know I am getting experience daily by reading such good posts.
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.
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.
There is certainly a great deal to find out about this subject.
I love all the points you made.
If you are going for most excellent contents like myself, just
pay a visit this site every day because it offers feature contents, thanks
Wow, wonderful blog layout! How lengthy have you ever been blogging for?
you make blogging glance easy. The overall glance of your web site is fantastic,
let alone the content material!
Thanks very interesting blog!
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!
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?
It’s very effortless to find out any matter on net as compared to textbooks, as
I found this article at this web site.
Nice post. I was checking continuously this weblog and I’m
inspired! Very helpful info specially the last part :
) I maintain such information a lot. I was seeking this particular
info for a very long time. Thanks and good luck.
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.
Great site. Lots of helpful info here. I am sending it to several pals ans also sharing in delicious.
And obviously, thank you to your sweat!
Hi, I read your blogs on a regular basis. Your writing style is witty,
keep doing what you’re doing!
For latest information you have to pay a quick visit internet and
on web I found this site as a finest website for
hottest updates.
There’s definately a lot to find out about this issue.
I really like all the points you have made. pof natalielise
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!
Hurrah! After all I got a website from where I be capable of in fact take
useful data regarding my study and knowledge.
Thanks for some other wonderful post. Where else could
anybody get that kind of information in such a perfect means of writing?
I have a presentation next week, and I’m on the search for such
info.
This piece of writing will help the internet visitors for building
up new blog or even a weblog from start to end.
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
These are truly impressive ideas in regarding blogging.
You have touched some pleasant factors here.
Any way keep up wrinting.
There is definately a lot to find out about this topic.
I like all of the points you have made.
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
Your way of telling all in this post is genuinely nice, all can simply be aware of it, Thanks a lot.
Thanks for sharing your thoughts on descargar facebook.
Regards
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!
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.
Hi there colleagues, how is the whole thing, and what
you would like to say about this piece of writing, in my view its in fact remarkable in favor
of me.
Asking questions are actually nice thing if you are not understanding anything totally, except this post gives fastidious
understanding even.
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!!
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!
Everyone loves what you guys are up too. This type
of clever work and reporting! Keep up the fantastic works guys I’ve included you guys
to my own blogroll.
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.
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
Hello, I enjoy reading all of your post.
I like to write a little comment to support you.
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.
Inspiring story there. What happened after? Good luck!
I am regular visitor, how are you everybody? This article posted at this website is really good.
I enjoy looking through an article that will make people think.
Also, many thanks for allowing for me to comment!
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.
Very quickly this web page will be famous among all blog
people, due to it’s fastidious articles or reviews
What’s Going down i’m new to this, I stumbled upon this I have found
It absolutely useful and it has helped me out loads. I’m hoping to give
a contribution & help other users like its aided me.
Good job.
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!
What’s up mates, how is all, and what you desire to say on the topic of this piece of writing, in my
view its actually remarkable in favor of me.
I think the admin of this web site is genuinely working hard in support of his web site, since here every information is quality based stuff.
Quality content is the key to be a focus for the
people to go to see the website, that’s what this web page is providing.
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
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
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!
I like the helpful info you provide in your articles. I will bookmark
your weblog and check again here frequently. I am
quite certain I’ll learn lots of new stuff right here!
Best of luck for the next!
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.
Hi! Do you know if they make any plugins to protect against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on.
Any suggestions?
Hello, all is going fine here and ofcourse every one is
sharing facts, that’s truly good, keep up writing.
I read this paragraph fully on the topic of the comparison of most recent and preceding technologies,
it’s remarkable article.
You need to be a part of a contest for one of the most useful websites on the internet.
I most certainly will highly recommend this web site!
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.
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!
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!
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.
Hello there! Would you mind if I share your blog with my twitter
group? There’s a lot of folks that I think would really appreciate your
content. Please let me know. Thanks
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. . . . . .
What’s up mates, its wonderful article on the topic of educationand entirely
explained, keep it up all the time.
I constantly spent my half an hour to read this website’s
articles or reviews daily along with a cup of coffee.
Great post! We are linking to this great content on our
website. Keep up the good writing.
Thanks for finally writing about >【日常小测】友好城市 – Qizy’s Database <Liked it!
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!
I love what you guys tend to be up too. Such clever work and reporting!
Keep up the great works guys I’ve incorporated you guys
to my personal blogroll.
If some one desires expert view regarding running a blog afterward i propose him/her to go to see this
weblog, Keep up the good work.
Thanks to my father who shared with me regarding this blog, this weblog is truly amazing.
Hello Dear, are you truly visiting this site on a regular basis,
if so after that you will definitely get nice know-how.
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!
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.
What a information of un-ambiguity and preserveness of precious experience concerning unexpected emotions.
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
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.