相关链接
题目传送门：http://uoj.ac/problem/77
神犇题解：http://www.cnblogs.com/geng4512/p/5296863.html
解题报告
我们发现如果忽略\(1<j<i\)这个限制，再假设\({l_i} = {r_i}\)
这样的话，直接上最小割就好
现在考虑\({l_i} < {r_i}\)
这样的话，用线段树优化建图就可以啦！
再考虑\(1<j<i\)这个限制
这样的话，用函数式线段树就可以啦！
感觉是VFK强行套数据结构啊！
另外还有BZOJ 3218可以双倍经验！
话说BZOJ上那些\(200ms+\)的神犇都是用的什么算法啊？
怎么这么快啊！
Code
#include<bits/stdc++.h>
using namespace std;
const int N = 200000+9;
const int M = 2000000;
const int INF = 1000000000;
int n,m,S,T,vout,head[N],nxt[M],to[M],flow[M];
int tot,_hash[N],A[N],W[N],B[N],LL[N],RR[N],P[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline void Add_Edge(int u, int v, int f = INF, int t = 0) {
static int E = 1; vout += f * t;
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}
class Network_Flow{
int cur[N],dis[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
memcpy(cur, head, sizeof(head));
ret += DFS(S, INF);
}
return ret;
}
private:
inline bool BFS() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) {
if (dis[to[i]] > INF && flow[i]) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
}
return dis[T] < INF;
}
int DFS(int w, int f) {
if (w == T) return f;
else {
int ret = 0;
for (int tmp,&i=cur[w];i;i=nxt[i]) {
if (dis[to[i]] == dis[w] + 1 && flow[i]) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) break;
}
}
return ret;
}
}
}Dinic;
namespace Persistent_Segment_Tree{
#define PST Persistent_Segment_Tree
int ch[N][2],root[N],cnt,pur,sur,L,R;
void insert(int p, int &w, int l, int r, int f = 0) {
if (w = ++cnt, p) {
ch[w][0] = ch[p][0];
ch[w][1] = ch[p][1];
Add_Edge(p, w);
}
if (f) Add_Edge(w, f);
if (l < r) {
int mid = l + r + 1 >> 1;
if (pur < mid) insert(ch[p][0], ch[w][0], l, mid-1, w);
else insert(ch[p][1], ch[w][1], mid, r, w);
} else Add_Edge(sur, w);
}
inline void insert(int p, int v) {
pur = v; sur = p;
insert(root[p-1], root[p], 1, tot);
}
void modify(int w, int l, int r) {
if (!w) return;
else if (L <= l && r <= R) Add_Edge(w, pur);
else {
int mid = l + r + 1 >> 1;
if (L < mid) modify(ch[w][0], l, mid-1);
if (mid <= R) modify(ch[w][1], mid, r);
}
}
inline void modify(int p, int node, int l, int r) {
pur = node; L = l; R = r;
modify(root[p], 1, tot);
}
};
int main() {
n = read(); PST::cnt = n << 1;
S = 0; T = N - 1;
for (int i=1;i<=n;i++) {
_hash[++tot] = A[i] = read();
B[i] = read();
W[i] = read();
_hash[++tot] = LL[i] = read();
_hash[++tot] = RR[i] = read();
P[i] = read();
}
sort(_hash+1, _hash+1+tot);
tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
for (int i=1;i<=n;i++) {
A[i] = lower_bound(_hash+1, _hash+1+tot, A[i]) - _hash;
LL[i] = lower_bound(_hash+1, _hash+1+tot, LL[i]) - _hash;
RR[i] = lower_bound(_hash+1, _hash+1+tot, RR[i]) - _hash;
}
for (int i=1,l,r;i<=n;i++) {
PST::insert(i, A[i]);
Add_Edge(i, T, B[i], 1);
Add_Edge(S, i, W[i], 1);
PST::modify(i-1, i+n, LL[i], RR[i]);
Add_Edge(i+n, i, P[i]);
}
printf("%d\n",vout-Dinic.MaxFlow());
return 0;
}
You could certainly see your enthusiasm within the article you write.
The world hopes for more passionate writers such
as you who aren’t afraid to mention how they believe. All the time go after your heart.
Ahaa, its pleasant discussion on the topic of this post at this place at this
webpage, I have read all that, so at this time me also commenting here.
Hello there I am so glad I found your web site, I really
found you by mistake, while I was researching on Google for something else, Anyways I am here
now and would just like to say kudos for a marvelous post and a all round thrilling blog (I also love the theme/design), I don’t have
time to read it all at the moment but I have bookmarked it and also added in your RSS feeds, so when I have time I
will be back to read a lot more, Please do keep up the excellent jo.
I every time emailed this webpage post page to all my friends,
for the reason that if like to read it then my links will too.
Hi there, I discovered your web site by the use of
Google even as looking for a comparable matter,
your web site came up, it looks great. I’ve bookmarked it in my google bookmarks.
Hi there, simply changed into aware of your weblog via Google,
and found that it’s really informative. I’m gonna watch out for brussels.
I will appreciate in the event you proceed this in future.
Lots of folks might be benefited from your writing.
Cheers!
I got this web page from my buddy who shared with me regarding this website
and at the moment this time I am visiting this site and reading very
informative content here.
It’s actually a cool and helpful piece of information. I am
happy that you simply shared this helpful info with us.
Please keep us up to date like this. Thank you for sharing.
Someone necessarily assist to make severely articles I’d
state. This is the very first time I frequented your
web page and so far? I surprised with the research you made to make this particular put up amazing.
Excellent activity!
I’m gone to inform my little brother, that he should also pay a visit this blog on regular
basis to obtain updated from most recent gossip.
Greetings from Florida! I’m bored to tears at work so I decided to check out your site on my iphone
during lunch break. I really like the knowledge you present here and can’t wait to take a look when I get home.
I’m shocked at how fast your blog loaded on my cell phone ..
I’m not even using WIFI, just 3G .. Anyhow, excellent site!
I’ve been browsing online more than 3 hours today, yet
I never found any interesting article like yours.
It’s pretty worth enough for me. In my opinion, if all website owners and bloggers made
good content as you did, the internet will be much more useful than ever before.
Hey I know this is off topic but I was wondering if you knew
of any widgets I could add to my blog that automatically
tweet my newest twitter updates. I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would have some experience with something like this.
Please let me know if you run into anything. I truly enjoy reading your blog and I look forward to
your new updates.
I’m really impressed along with your writing talents and also with the layout in your blog.
Is this a paid subject matter or did you customize it your self?
Anyway stay up the nice quality writing, it’s uncommon to peer a great weblog like this one these days..
Hi, yeah this post is in fact fastidious and I have learned
lot of things from it regarding blogging. thanks.
Hey! 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 blog goes
over a lot of the same topics as yours and I think 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!
Hey! I know this is somewhat off topic but I
was wondering which blog platform are you using for this website?
I’m getting tired of WordPress because I’ve had issues with hackers and I’m looking at options for
another platform. I would be great if you could point me in the direction of a good platform.
excellent submit, very informative. I wonder why the opposite specialists of this sector don’t notice this.
You should continue your writing. I am sure, you’ve a great readers’
base already!
Howdy, There’s no doubt that your website could possibly be having browser compatibility issues.
When I take a look at your blog in Safari, it looks fine but when opening
in IE, it has some overlapping issues. I merely wanted to provide
you with a quick heads up! Other than that, great site!
Hey there! Someone in my Facebook group shared this website
with us so I came to take a look. I’m definitely loving the information. I’m
bookmarking and will be tweeting this to my followers!
Terrific blog and wonderful design.
I am regular visitor, how are you everybody? This post posted at this website is in fact good.
If you wish for to get a great deal from this paragraph then you have to apply
these techniques to your won web site. pof natalielise
hello there and thank you for your info – I’ve definitely picked up something new from right here.
I did however expertise a few technical points using this web site, as
I experienced to reload the web site many times previous to I could get it to load
correctly. I had been wondering if your web hosting is OK?
Not that I am complaining, but sluggish loading instances times will often 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 could look out
for a lot more of your respective interesting content. Ensure that you update this again soon.
What’s up i am kavin, its my first time to commenting anywhere, when i read this post i thought i could also make comment due to
this brilliant article.
Hi there very nice blog!! Man .. Beautiful ..
Amazing .. I will bookmark your site and take the feeds additionally?
I’m glad to search out numerous useful info right here
within the publish, we’d like develop extra strategies in this regard, thanks for sharing.
. . . . .
You are so awesome! I don’t suppose I’ve read through a single thing like that before.
So nice to discover another person with some unique thoughts on this issue.
Seriously.. thanks for starting this up. This site is one thing that
is required on the web, someone with a bit of originality!
natalielise plenty of fish
Hi there! This article couldn’t be written any better! Going through this article reminds
me of my previous roommate! He constantly kept talking about this.
I will send this post to him. Fairly certain he’s going to have a very good read.
Thanks for sharing!
Hmm it appears like your site ate my first comment (it was extremely long) so I guess I’ll just sum it up what I wrote and say, I’m thoroughly
enjoying your blog. I too am an aspiring blog blogger but I’m still new
to the whole thing. Do you have any helpful hints
for beginner blog writers? I’d genuinely appreciate it.
I every time emailed this website post page to all my contacts,
because if like to read it then my contacts will too.
Thanks for ones marvelous posting! I really enjoyed reading it, you could be a great author.I will make sure to
bookmark your blog and definitely will come back at some point.
I want to encourage that you continue your great work,
have a nice holiday weekend!
Way cool! Some very valid points! I appreciate you penning this article plus the rest
of the site is very good.
For most up-to-date news you have to visit the web and on the web I found this
site as a most excellent web page for hottest updates.
I visit daily some web sites and websites to read content,
except this blog gives quality based content.
For newest news you have to pay a visit internet and on internet I found this
site as a most excellent web site for newest updates.
I love your blog.. very nice colors & theme.
Did you create this website yourself or did you hire someone to do it for
you? Plz respond as I’m looking to design my
own blog and would like to find out where u got this from.
appreciate it
If you desire to increase your know-how only keep visiting this site and
be updated with the latest news update posted here.
Have you ever considered writing an ebook or guest authoring on other blogs?
I have a blog centered on the same subjects you discuss and would love to have you share some stories/information. I know my readers would value your
work. If you are even remotely interested, feel free to shoot me an e mail.
Hello mates, its great article regarding tutoringand entirely defined, keep it up all the time.
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 throw away your intelligence on just posting videos to your blog when you could be giving us something informative to read?
Its like you learn my mind! You seem to know a lot approximately this, like you wrote the e book in it or
something. I think that you simply could do with some percent to pressure the
message house a little bit, but instead of that, that is great blog.
An excellent read. I will definitely be back.
Hi to every one, the contents present at this website are genuinely awesome for people experience, well, keep up the good work fellows.
If some one needs expert view on the topic of running a blog after that i suggest him/her to pay a
quick visit this weblog, Keep up the fastidious job.
For most recent news you have to pay a visit the web and on the
web I found this site as a best website for hottest updates.
I know this if off topic but I’m looking into starting my own blog and was curious what all is
required to get set up? I’m assuming having a blog like yours would cost
a pretty penny? I’m not very web smart so I’m not 100% certain. Any recommendations or
advice would be greatly appreciated. Thanks
Howdy! This blog post could not be written any better!
Reading through this post reminds me of my previous roommate!
He constantly kept talking about this. I most certainly will send this post to him.
Fairly certain he’ll have a great read. I appreciate you
for sharing!
When I initially commented I clicked the “Notify me when new comments are added” checkbox and now each time a comment is
added I get four emails with the same comment. Is there any way you can remove me from that service?
Cheers!
Hello mates, its great piece of writing about educationand completely explained, keep it up all
the time.
What’s up, this weekend is nice for me, as this time i am reading this great
educational piece of writing here at my house.
Hi! This post couldn’t be written any better! Reading through this post reminds
me of my old room mate! He always kept chatting about this.
I will forward this page to him. Fairly certain he will have a good read.
Thank you for sharing!
Thank you for another magnificent article. Where else may
anyone get that type of information in such an ideal method of writing?
I’ve a presentation next week, and I am on the look for such information.
Hey there! I just want to offer you a big thumbs up for your
excellent information you have got right here on this
post. I am returning to your blog for more soon.
I think the admin of this web page is truly working hard for his web page,
because here every material is quality based stuff.
This is a topic which is near to my heart… Best wishes!
Exactly where are your contact details though?
If you want to increase your familiarity simply keep visiting this website and
be updated with the most up-to-date information posted here.
Wonderful, what a web site it is! This weblog gives
valuable information to us, keep it up.
I think this is among the most important information for me.
And i’m glad reading your article. But should remark on few general things, The site style is ideal, the articles is
really excellent : D. Good job, cheers
This is really interesting, You are a very skilled blogger.
I have joined your feed and look forward to seeking more
of your excellent post. Also, I’ve shared your web site in my social networks!
I have learn a few good stuff here. Definitely worth bookmarking for revisiting.
I wonder how much attempt you set to create this sort of great informative web site.
This is really interesting, You are a very skilled blogger.
I’ve joined your feed and look forward to seeking more of your excellent post.
Also, I’ve shared your website in my social networks!
Awesome! Its in fact amazing piece of writing, I have
got much clear idea on the topic of from this article.
Great post. I was checking continuously this weblog and I am inspired!
Extremely useful info specifically the closing part 🙂 I care
for such info a lot. I was looking for this certain info for a long time.
Thank you and best of luck.
Simply wish to say your article is as astounding.
The clarity for your post is just nice and i could assume you’re a professional on this subject.
Fine along with your permission allow me to take hold of
your feed to stay up to date with drawing close post. Thanks 1,000,000 and please continue the gratifying work.
You actually make it appear really easy with your presentation but I find this
matter to be really something which I feel I’d by no means understand.
It seems too complicated and very wide for me.
I am taking a look ahead on your next put up, I will attempt to get the dangle of it!
I am curious to find out what blog system you
have been using? I’m having some minor security issues with my
latest website and I would like to find something more safeguarded.
Do you have any recommendations?
May I simply say what a relief to find somebody who
truly understands what they are discussing on the internet.
You actually realize how to bring an issue to light and make it important.
More people really need to look at this and understand this side of your story.
It’s surprising you are not more popular given that you definitely
have the gift.
My spouse and I stumbled over here different web address and thought I might as well
check things out. I like what I see so i am just following you.
Look forward to looking into your web page repeatedly.
fantastic points altogether, you simply received a logo new reader. What may you suggest about your publish that you simply made some days in the past? Any sure?
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 throw away your intelligence on just posting
videos to your site when you could be giving us something enlightening to read?
Hey I know this is off topic but I was wondering if you knew of any widgets
I could add to my blog that automatically tweet my newest twitter updates.
I’ve been looking for a plug-in like this for quite some
time and was hoping maybe you would have some experience with something like this.
Please let me know if you run into anything. I truly enjoy reading your blog and I look forward to your new updates.
Hello, I check your blogs on a regular basis. Your writing style is witty, keep it up!
Wonderful beat ! I would like to apprentice while you
amend your site, how could i subscribe for a blog web
site? The account aided me a acceptable deal. I had been tiny bit acquainted of this your broadcast provided bright
clear concept
Your style is so unique in comparison to other people I have read stuff from.
I appreciate you for posting when you have the opportunity, Guess I will just bookmark this blog.
Can I simply just say what a relief to discover an individual who really knows what they are talking about on the web.
You definitely understand how to bring an issue
to light and make it important. More people need to look at this and understand
this side of the story. I was surprised you are not more popular since you
definitely have the gift.
Great goods from you, man. I have understand your stuff previous to and you
are just too magnificent. I really like what you’ve acquired here, really like what you are saying and the
way in which you say it. You make it entertaining
and you still take care of to keep it wise. I cant wait
to read much more from you. This is actually a terrific web site.
Hurrah, that’s what I was seeking for, what a data!
existing here at this webpage, thanks admin of
this web site.
Hello There. I found your blog using msn. This is a really
well written article. I’ll be sure to bookmark it and come back to read more of your useful info.
Thanks for the post. I’ll certainly return.
I’m not sure why but this weblog 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.
Thanks for sharing your thoughts on sling tv. Regards
of course like your website but you need to check the spelling on several of your posts. Several of them are rife with spelling issues and I find it very bothersome to tell the truth nevertheless I’ll certainly come back again.