相关链接
题目传送门：http://agc015.contest.atcoder.jp/tasks/agc015_e
解题报告
我们发现：对于任意一个时刻，一个病原体引发的感染者一定是一个区间
那么问题转化为选一些线段来覆盖整个序列，这个用可以线性维护
总的时间复杂度：$O(n \log n)$
Code
#include<bits/stdc++.h>
#define LL long long
#define lowbit(x) ((x)&-(x))
using namespace std;
const int N = 200009;
const int MOD = 1000000007;
int n, np[N], arr[N];
struct Data{
int x, v;
inline bool operator < (const Data &D) const {
return x < D.x || (x == D.x && v < D.v);
}
}d[N], seg[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 bool cmpv(int aa, int bb) {
return d[aa].v < d[bb].v;
}
class Fenwick_Tree{
int sum[N], uve, cur = 1;
public:
inline void modify(int p, int x) {
uve = (uve + x) % MOD;
sum[p] = (sum[p] + x) % MOD;
}
inline int query(int p) {
while (cur < p) {
++cur;
sum[cur] = (sum[cur] + sum[cur - 1]) % MOD;
}
return ((uve - sum[p - 1]) + MOD) % MOD;
}
}BIT;
int main() {
n = read();
for (int i = 1; i <= n; i++) {
d[i].x = read();
d[i].v = read();
arr[i] = i;
}
sort(d + 1, d + 1 + n);
sort(arr + 1, arr + 1 + n, cmpv);
for (int i = 1; i <= n; i++) {
np[arr[i]] = i;
}
for (int i = 1, cur = 0; i <= n; ++i) {
seg[i].x = cur = max(cur, np[i]);
}
for (int i = n, cur = n + 1; i; --i) {
seg[i].v = cur = min(cur, np[i]);
}
sort(seg + 1, seg + 1 + n);
BIT.modify(1, 1);
for (int i = 1; i <= n; i++) {
int tmp = BIT.query(seg[i].v);
BIT.modify(seg[i].x + 1, tmp);
}
printf("%d\n", BIT.query(n + 1));
return 0;
}
哇塞，居然是沙发？留个名
I’m amazed, I must say. Seldom do I encounter a blog that’s
both equally educative and interesting, and let me tell you, you have
hit the nail on the head. The problem is an issue that too few men and women are speaking intelligently about.
I’m very happy that I came across this in my search for something regarding this.
Keep on working, great job!
What’s up, I log on to your blog on a regular basis. Your story-telling style is witty, keep it up!
If you would like to get a good deal from this article then you have to apply these methods to your won blog.
Hey there! I know this is kinda off topic however , I’d figured I’d ask.
Would you be interested in trading links or maybe guest authoring a blog article or vice-versa?
My website covers a lot of the same subjects as yours and I think
we could greatly benefit from each other. If you might be interested feel free to
shoot me an e-mail. I look forward to hearing from you! Great
blog by the way!
You actually make it seem so easy with your presentation but I find this
matter to be actually something that I think I would never understand.
It seems too complicated and extremely broad for me.
I am looking forward for your next post, I’ll try to get the hang of it!
Thank you a bunch for sharing this with all folks you really realize what you are speaking approximately!
Bookmarked. Please also visit my site =). We may have
a hyperlink trade contract among us
Hello! Do you know if they make any plugins
to help with Search Engine Optimization? I’m trying to get my blog
to rank for some targeted keywords but I’m not seeing very good results.
If you know of any please share. Appreciate it!
What’s up to every body, it’s my first visit of this webpage; this web site
contains awesome and genuinely good material in support of readers.
Excellent post. I was checking constantly this blog and I
am impressed! Very useful info specially the last section 🙂 I care for such
info much. I was looking for this certain information for a very lengthy
time. Thank you and best of luck.
I wanted to thank you for this fantastic read!!
I definitely enjoyed every little bit of it.
I have you book-marked to check out new things you post…
Everything is very open with a really clear explanation of the challenges.
It was truly informative. Your site is useful.
Many thanks for sharing!
Hello there! I could have sworn I’ve been to this website before
but after going through some of the posts I realized it’s new to me.
Nonetheless, I’m definitely delighted I stumbled upon it and I’ll be book-marking it and
checking back regularly!
It’s amazing in favor of me to have a web site, which is
beneficial designed for my experience. thanks admin
Thanks for one’s marvelous posting! I quite enjoyed reading it, you
might be a great author. I will remember to bookmark your blog and definitely
will come back down the road. I want to encourage you to definitely continue your great work, have
a nice day!
I always emailed this website post page to all my associates, since if like
to read it after that my contacts will too.
My brother recommended I may like this blog.
He was entirely right. This publish actually made my day.
You cann’t imagine simply how much time I had spent for this info!
Thanks! natalielise pof
Howdy great blog! Does running a blog such as this
require a massive amount work? I’ve absolutely no expertise in computer
programming but I was hoping to start my own blog in the near future.
Anyways, should you have any ideas or techniques for new blog
owners please share. I understand this is off subject but I
just needed to ask. Appreciate it!
Yesterday, while I was at work, my sister stole my apple ipad and tested to
see if it can survive a forty foot drop, just so she can be a youtube sensation. My iPad is now destroyed and she has 83 views.
I know this is totally off topic but I had to share it with someone!
Hi, just wanted to say, I loved this post.
It was practical. Keep on posting!
My brother suggested I might like this website.
He was totally right. This post actually made my day.
You can not imagine just how much time I had spent for this information! Thanks!
There is definately a lot to find out about this subject.
I really like all the points you have made. natalielise pof
Hey! Someone in my Myspace group shared this website with us so I
came to check it out. I’m definitely loving the information. I’m book-marking and
will be tweeting this to my followers! Wonderful
blog and great design.
I constantly spent my half an hour to read this web site’s articles everyday along with
a mug of coffee.
Touche. Great arguments. Keep up the amazing spirit.
Hello there! Do you use Twitter? I’d like to follow you if that would be ok.
I’m definitely enjoying your blog and look forward to new updates.
Hey there! I know this is kinda off topic nevertheless I’d figured I’d ask.
Would you be interested in exchanging links or maybe guest
writing a blog article or vice-versa? My blog covers a
lot of the same topics as yours and I feel we could greatly benefit from each
other. If you might be interested feel free to send me an e-mail.
I look forward to hearing from you! Fantastic blog by the
way!
Hi! I just wanted to ask if you ever have any trouble with hackers?
My last blog (wordpress) was hacked and I ended up losing months of hard work due to no data backup.
Do you have any solutions to stop hackers?
Woah! I’m really enjoying the template/theme of this website.
It’s simple, yet effective. A lot of times it’s hard to
get that “perfect balance” between user friendliness and visual appeal.
I must say you have done a superb job with
this. Additionally, the blog loads very quick for me on Internet explorer.
Superb Blog!
excellent points altogether, you simply gained a emblem new
reader. What might you recommend about your submit that you
made some days ago? Any sure?
You really make it seem so easy with your presentation but I find this matter to
be really something which I think I would never understand.
It seems too complex and extremely broad for me. I’m looking forward
for your next post, I’ll try to get the hang
of it!
This design is wicked! You most certainly know how to keep a
reader amused. Between your wit and your videos, I was almost moved to start my own blog (well,
almost…HaHa!) Wonderful job. I really loved what you had to say, and more than that,
how you presented it. Too cool!
Way cool! Some very valid points! I appreciate you penning this write-up plus the rest of the website is
very good.
Hey terrific website! Does running a blog like this take a great
deal of work? I’ve virtually no expertise in programming but I had been hoping
to start my own blog in the near future. Anyway, should you have any ideas or
tips for new blog owners please share. I know this is off topic but I just had to
ask. Thanks!
You ought to be a part of a contest for one of the highest quality
websites on the internet. I will highly recommend this web
site!
I was very pleased to find this page. I need to to thank you
for your time due to this wonderful read!!
I definitely appreciated every part of it and I have you
saved to fav to check out new information on your website.
Excellent way of explaining, and fastidious article to get facts about my
presentation subject, which i am going to deliver in academy.
Whoa! This blog looks exactly like my old one! It’s on a completely different
topic but it has pretty much the same page layout and design. Great choice of colors!
Hi there colleagues, pleasant article and good
urging commented at this place, I am actually enjoying by these.
Howdy just wanted to give you a brief heads up and let
you know a few of the pictures aren’t loading correctly. I’m not sure why but I think its a linking issue.
I’ve tried it in two different browsers and both show the
same results.
bookmarked!!, I like your web site!
When some one searches for his necessary thing,
therefore he/she wants to be available that in detail, thus that thing
is maintained over here.
I am sure this post has touched all the internet visitors, its really really nice article on building up
new website.
It’s fantastic that you are getting ideas from this piece of writing as well as from our argument
made here.
Oh my goodness! Amazing article dude! Thank you so much, However I am
encountering issues with your RSS. I don’t understand the reason why
I can’t subscribe to it. Is there anybody having similar RSS problems?
Anybody who knows the solution can you kindly respond? Thanks!!
This is very 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 have shared your web site in my social networks!
This is a topic which is close to my heart… Cheers! Where are your contact details though?
I got this web site from my pal who shared with me about this web site and now this time I am visiting this site and reading very informative content
here.
I like what you guys are up too. Such clever work and
exposure! Keep up the amazing works guys I’ve added you guys to my personal blogroll.
Woah! I’m really enjoying the template/theme of
this website. It’s simple, yet effective. A
lot of times it’s very hard to get that “perfect balance” between superb usability and visual appeal.
I must say you have done a superb job with this. Also, the blog loads very quick for me on Firefox.
Outstanding Blog!
I have been surfing on-line more than 3 hours lately,
but I by no means discovered any interesting article like yours.
It is pretty price enough for me. Personally, if all site owners and
bloggers made just right content as you did,
the internet will probably be a lot more useful than ever
before.
I’m not sure why but this website is loading very slow for me.
Is anyone else having this issue or is it a problem on my
end? I’ll check back later on and see if the problem still exists.
Hi there, all the time i used to check weblog posts here early in the dawn, for the reason that i love to
find out more and more.
Terrific work! This is the type of info that should be shared
around the web. Disgrace on Google for not positioning this post upper!
Come on over and visit my website . Thanks =)
This is a good tip especially to those fresh to the blogosphere.
Brief but very accurate information… Many thanks for sharing this one.
A must read post!
Hey very nice website!! Man .. Beautiful .. Wonderful ..
I will bookmark your blog and take the feeds
additionally? I’m happy to find numerous helpful info right here within the submit,
we want work out extra strategies in this regard, thank you for sharing.
. . . . .
If you desire to grow your experience only keep visiting this
website and be updated with the most recent
news update posted here.
Fabulous, what a weblog it is! This web
site gives valuable information to us, keep it up.
I just like the helpful info you supply on your articles.
I’ll bookmark your blog and take a look at once
more here frequently. I am quite certain I’ll be informed a lot of
new stuff proper here! Best of luck for the following!
It’s very effortless to find out any matter on web as compared
to textbooks, as I found this paragraph at this
web page.
Piece of writing writing is also a excitement, if you be familiar with then you can write if not it is difficult to write.
Just wanna remark on few general things, The website layout is perfect, the subject material is very excellent : D.
What a information of un-ambiguity and preserveness of precious knowledge regarding unexpected
emotions.
Generally I don’t read post on blogs, however I would like to say that this
write-up very forced me to check out and do it!
Your writing style has been surprised me. Thanks,
very nice article.
It’s awesome to pay a quick visit this site and reading the views of all friends on the
topic of this paragraph, while I am also zealous of getting familiarity.
Write more, thats all I have to say. Literally, it seems as though you relied on the video to make your
point. You clearly know what youre talking about, why
waste your intelligence on just posting videos to your blog when you could be giving us something informative to read?
The other day, while I was at work, my cousin stole my apple ipad and tested to
see if it can survive a 25 foot drop, just so she can be a youtube sensation. My apple
ipad is now broken and she has 83 views. I know this is entirely off topic but I had to share
it with someone!
Hello, just wanted to mention, I liked this blog post.
It was funny. Keep on posting!
Hi there i am kavin, its my first time to commenting anywhere, when i read this piece of writing i thought i
could also create comment due to this sensible article.
Hello mates, pleasant article and good arguments commented at this place, I
am genuinely enjoying by these.
I all the time used to study piece of writing in news papers but now
as I am a user of web so from now I am using net for articles,
thanks to web.
Hi, There’s no doubt that your website could possibly be having browser compatibility problems.
Whenever I take a look at your blog in Safari, it looks fine however, when opening in I.E., it’s got
some overlapping issues. I merely wanted to give you
a quick heads up! Besides that, excellent
website!
We’re a gaggle of volunteers and starting a brand new scheme in our community.
Your website provided us with valuable information to work on. You have performed a formidable job
and our entire community will be thankful to you.
hi!,I really like your writing very much! percentage we communicate more about your article on AOL? I need a specialist on this area to unravel my problem. May be that’s you! Taking a look forward to look you.
Thank you ever so for you article.Really thank you! Really Great.