相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4826
神犇题解:http://www.cnblogs.com/Enceladus/p/6735887.html
解题报告
这题建出笛卡尔树,之后就是区间加、区间询问
于是将询问离线,用线段树维护一下就好了
总时间复杂度:$O(n \log n)$
至于笛卡尔树那一块,我们可以看作一个分治
而与最大值相关的题,分治是常见解法
所以这题还是很容易想到的吧
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 200009; const int NN = N << 1; const int M = 18; int n,m,p1,p2,val[N]; LL ans[N]; vector<int> q1[N]; vector<pair<int,int> > q2[N],q3[N]; struct Query{int l,r,id;}q[N]; inline bool cmp1(const Query &A, const Query &B) {return A.r < B.r;} inline bool cmp2(const Query &A, const Query &B) {return A.l > B.l;} 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; } class Sparse_Table{ int mx[M][N],pos[M][N],lg[N]; public: inline void init(int *arr) { for (int i=1;i<=n;i++) { mx[0][i] = arr[i]; pos[0][i] = i; } for (int l=1,j=1;l*2<=n;j++,l<<=1) { for (int i=1;i<=n-l;i++) { if (mx[j-1][i] >= mx[j-1][i+l]) { pos[j][i] = pos[j-1][i]; mx[j][i] = mx[j-1][i]; } else { pos[j][i] = pos[j-1][i+l]; mx[j][i] = mx[j-1][i+l]; } } } for (int i=2;i<=n;i++) { lg[i] = lg[i>>1] + 1; } } inline int query(int l, int r) { int t = lg[r-l+1], j = 1 << t; if (mx[t][l] >= mx[t][r-j+1]) return pos[t][l]; else return pos[t][r-j+1]; } }ST; void solve(int l, int r) { if (l == r - 1) { return; } else { int pos = ST.query(l+1, r-1); if (l) q1[pos].push_back(l); if (r <= n) q1[r].push_back(pos); if (r <= n && pos - l > 1) q2[r].push_back(make_pair(l + 1, pos - 1)); if (l && r - pos > 1) q3[l].push_back(make_pair(pos + 1, r - 1)); solve(l, pos); solve(pos, r); } } class Segment_Tree{ int cnt; LL AnsTmp; struct Node{ Node *ch[2]; int len; LL sum,tag; }p[NN],*root; public: inline void init() { cnt = 0; build(root, 1, n); } inline void modify(int pos, int delta) { Node *w = root; int l = 1, r = n, mid; while (l <= r) { w->sum += delta; if (l == r) break; mid = l + r + 1 >> 1; if (pos < mid) w = w->ch[0], r = mid - 1; else w = w->ch[1], l = mid; } } inline void modify(int l, int r, int delta) { modify(root, 1, n, l, r, delta); } inline LL query(int l, int r) { AnsTmp = 0; query(root, 1, n, l, r); return AnsTmp; } private: inline void pushdown(Node *w) { w->ch[0]->sum += w->ch[0]->len * w->tag; w->ch[1]->sum += w->ch[1]->len * w->tag; w->ch[0]->tag += w->tag; w->ch[1]->tag += w->tag; w->tag = 0; } void query(Node *w, int l, int r, int L, int R) { if (L <= l && r <= R) { AnsTmp += w->sum; } else { if (w->tag) pushdown(w); int mid = l + r + 1 >> 1; if (L < mid) query(w->ch[0], l, mid-1, L, R); if (mid <= R) query(w->ch[1], mid, r, L, R); } } void modify(Node *w, int l, int r, int L, int R, int delta) { if (L <= l && r <= R) { w->sum += (LL)delta * w->len; w->tag += delta; } else { if (w->tag) pushdown(w); int mid = r + l + 1 >> 1; if (L < mid) modify(w->ch[0], l, mid-1, L, R, delta); if (mid <= R) modify(w->ch[1], mid, r, L, R, delta); w->sum = w->ch[0]->sum + w->ch[1]->sum; } } void build(Node *&w, int l, int r) { w = &p[++cnt]; w->len = r - l + 1; w->sum = w->tag = 0; w->ch[0] = w->ch[1] = 0; if (l < r) { int mid = l + r + 1 >> 1; build(w->ch[0], l, mid-1); build(w->ch[1], mid, r); } } }SEG; int main() { n = read(); m = read(); p1 = read(); p2 = read(); for (int i=1;i<=n;i++) { val[i] = read(); } ST.init(val); solve(0, n+1); for (int i=1;i<=m;i++) { q[i].l = read(); q[i].r = read(); q[i].id = i; } sort(q+1, q+1+m, cmp1); SEG.init(); for (int i=1,pos=0;i<=m;i++) { while (pos < q[i].r) { pos++; for (int j=0;j<q1[pos].size();j++) { SEG.modify(q1[pos][j], p1); } for (int j=0;j<q2[pos].size();j++) { SEG.modify(q2[pos][j].first, q2[pos][j].second, p2); } } ans[q[i].id] += SEG.query(q[i].l, q[i].r); } sort(q+1, q+1+m, cmp2); SEG.init(); for (int i=1,pos=n+1;i<=m;i++) { while (pos > q[i].l) { pos--; for (int j=0;j<q3[pos].size();j++) { SEG.modify(q3[pos][j].first, q3[pos][j].second, p2); } } ans[q[i].id] += SEG.query(q[i].l, q[i].r); } for (int i=1;i<=m;i++) { printf("%lld\n",ans[i]); } return 0; }
楼下是疯子。哈哈
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!
Yes! Finally someone writes about gamefly free trial.
I have been surfing online more than 2 hours today, yet I never found any interesting article like yours.
It’s pretty worth enough for me. In my view, if all website owners and bloggers made good content as
you did, the web will be a lot more useful than ever before.
Hello, Neat post. There’s a problem along with your website in internet explorer,
could check this? IE nonetheless is the marketplace leader and a
big component of people will leave out your excellent writing due to this problem.
For newest news you have to pay a quick visit world wide web and on internet I found this site as a
most excellent web site for newest updates.
Hey! I know this is kind of 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 problems
with hackers and I’m looking at alternatives for another platform.
I would be great if you could point me in the direction of
a good platform.
I’m gone to inform my little brother, that he should
also visit this webpage on regular basis to get updated from most up-to-date reports.
Thank you for the auspicious writeup. It in fact was a amusement account it.
Look advanced to far added agreeable from you! By the way, how could we
communicate?
I love it when folks get together and share views.
Great website, continue the good work!
Your style is unique in comparison to other folks
I’ve read stuff from. I appreciate you for posting when you’ve got the
opportunity, Guess I’ll just bookmark this blog.
Hello to all, it’s actually a fastidious for me to go to see this site, it includes helpful Information. plenty of fish natalielise
I used to be able to find good advice from your content.
Thanks for sharing your thoughts about plenty of fish dating site.
Regards
Its like you read my mind! You appear to know so much about this, like you wrote the book in it or something.
I think that you could do with some pics to drive
the message home a little bit, but instead of that,
this is magnificent blog. A fantastic read. I will definitely be back.
I’m really enjoying the design and layout of your blog.
It’s a very easy on the eyes which makes it much more pleasant for me to come here and visit more often. Did you hire out a
developer to create your theme? Superb work! natalielise plenty of fish
Yes! Finally something about pof.
Hurrah! In the end I got a webpage from where I be able to in fact obtain useful information concerning my study and knowledge.
Greetings! I know this is kinda off topic but I was wondering which
blog platform are you using for this site?
I’m getting fed up 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.
plenty of fish natalielise
obviously like your web-site but you need to test the
spelling on several of your posts. A number of them
are rife with spelling issues and I in finding
it very troublesome to inform the reality on the other hand I’ll certainly come
again again.
Hi, I do think this is a great web site. I stumbledupon it 😉 I’m going to return yet again since i
have book-marked it. Money and freedom is the best way to change,
may you be rich and continue to guide others.
I take pleasure in, cause I discovered exactly what
I used to be looking for. You’ve ended my 4 day long hunt!
God Bless you man. Have a great day. Bye
Hi! Do you know if they make any plugins to help with
SEO? I’m trying to get my blog to rank for some targeted keywords
but I’m not seeing very good gains. If you know of any please share.
Thanks!
Wonderful site. A lot of helpful information here.
I’m sending it to some buddies ans also sharing in delicious.
And certainly, thanks for your effort!
Fabulous, what a webpage it is! This weblog gives useful facts to us,
keep it up.
I know this web site presents quality based
content and other data, is there any other site which gives these stuff in quality?
If you wish for to grow your knowledge only keep visiting this web site and be updated
with the hottest information posted here.
I was curious if you ever thought of changing the page layout of your site?
Its very well written; I love what youve got to say. But maybe
you could a little more in the way of content so people could connect with it better.
Youve got an awful lot of text for only having 1 or 2 pictures.
Maybe you could space it out better?
I always used to study paragraph in news papers but now as
I am a user of net so from now I am using net for content, thanks
to web.
Hi there, all the time i used to check webpage posts here early in the break
of day, because i like to gain knowledge of more and more.
Thanks on your marvelous posting! I definitely enjoyed reading
it, you’re a great author.I will make sure to bookmark your blog and will come back
very soon. I want to encourage you to continue your great posts, have a nice morning!
Hello would you mind stating which blog platform you’re working with?
I’m looking to start my own blog soon but I’m having a difficult time deciding between BlogEngine/Wordpress/B2evolution and Drupal.
The reason I ask is because your design seems different then most blogs
and I’m looking for something completely unique.
P.S My apologies for getting off-topic but I had to ask!
It’s remarkable designed for me to have a website, which is valuable in support of my knowledge.
thanks admin
Very good post. I am dealing with many of these issues as well..
Thanks for some other informative blog. The place else could I am getting that type of info written in such a perfect
method? I’ve a undertaking that I am simply now operating on, and I have been at
the glance out for such information.
I loved as much as you’ll receive carried out right here.
The sketch is attractive, your authored subject matter stylish.
nonetheless, you command get bought an edginess over that you wish be
delivering the following. unwell unquestionably come more
formerly again since exactly the same nearly a lot often inside case
you shield this increase.
Great items from you, man. I have be aware your stuff previous to and you’re simply extremely excellent.
I actually like what you’ve received here, really like what you’re
stating and the way wherein you are saying it. You
make it enjoyable and you still take care of to keep
it sensible. I can not wait to read much more from you. That is really a tremendous
website.
Hey There. I found your blog using msn. This is
an extremely well written article. I’ll make sure to bookmark it and come back to read more of your useful info.
Thanks for the post. I will definitely comeback.
Nice answer back in return of this matter with solid arguments and describing all regarding that.
Link exchange is nothing else but it is just placing the other person’s
weblog link on your page at appropriate place and other
person will also do similar for you.
Its like you read my mind! You appear to know so much about this, like you wrote the book in it or
something. I think that you can do with some pics to drive the message
home a little bit, but other than that, this is wonderful blog.
An excellent read. I will definitely be back.
What’s up mates, how is the whole thing, and what you want to say
about this post, in my view its genuinely amazing in favor of me.
Very nice blog post. I absolutely love this site.
Stick with it!
I’m extremely impressed with your writing skills as well as with the layout on your weblog.
Is this a paid theme or did you modify it yourself?
Anyway keep up the excellent quality writing, it
is rare to see a great blog like this one these days.
This design is incredible! You obviously know how to keep a reader entertained.
Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Wonderful job.
I really enjoyed what you had to say, and more than that, how you presented it.
Too cool!
I’m not sure where you are getting your info, but great topic.
I needs to spend some time learning much more or understanding more.
Thanks for wonderful information I was looking for this information for my mission.
Thank you a lot for sharing this with all people you really understand what you’re talking about!
Bookmarked. Kindly also visit my website =). We will have a
hyperlink trade agreement between us
When someone writes an piece of writing he/she keeps the plan of a
user in his/her brain that how a user can be aware of it. So
that’s why this paragraph is great. Thanks!
I always spent my half an hour to read this blog’s content daily along with a cup of coffee.
My brother suggested I may like this blog. He was once entirely
right. This submit truly made my day. You can not believe simply
how so much time I had spent for this info! Thanks!
My developer is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the costs.
But he’s tryiong none the less. I’ve been using Movable-type on numerous websites for about a year and am anxious 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 greatly appreciated!
Pretty nice post. I just stumbled upon your blog and
wanted to say that I have truly enjoyed surfing around your blog
posts. After all I will be subscribing to your rss
feed and I hope you write again soon!
I am really glad to read this web site posts which includes plenty of useful information, thanks for providing these kinds of data.
Good web site you have here.. It’s hard to find quality writing like yours nowadays.
I truly appreciate individuals like you! Take care!!
Howdy! 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?
This excellent website really has all of the information I wanted concerning this subject and
didn’t know who to ask.
What’s up to all, how is all, I think every one is getting more from this website,
and your views are fastidious for new visitors.
I have been surfing online more than 3 hours today, yet I never found any interesting article like
yours. It’s pretty worth enough for me. Personally, if all site owners and bloggers made good content as you did,
the web will be a lot more useful than ever before.
Howdy! This post couldn’t be written any better!
Reading through this post reminds me of my previous room mate!
He always kept chatting about this. I will forward this write-up to
him. Pretty sure he will have a good read. Thanks for sharing!
Hello there! I know this is somewhat off topic but I was wondering
which blog platform are you using for this website?
I’m getting sick and tired of WordPress because I’ve had
issues with hackers and I’m looking at options for another
platform. I would be fantastic if you could point
me in the direction of a good platform.
Wonderful article! That is the type of information that are meant to
be shared around the web. Disgrace on the search engines for no longer positioning this
post upper! Come on over and talk over with my site .
Thank you =)
If you want to grow your knowledge simply keep visiting this web site and be updated with the newest gossip posted
here.
Hello there! This article couldn’t be written any better!
Looking at this article reminds me of my previous roommate!
He continually kept talking about this. I’ll send
this post to him. Pretty sure he will have a great read.
I appreciate you for sharing!
Heya terrific blog! Does running a blog similar to this require
a large amount of work? I’ve virtually no knowledge of
coding but I had been hoping to start my own blog in the near future.
Anyhow, if you have any recommendations or techniques for new blog owners
please share. I understand this is off topic nevertheless I just
needed to ask. Many thanks!
When some one searches for his required thing, thus he/she wants to be available that in detail, therefore that thing is maintained over here.
Good day! I just would like to offer you a huge thumbs up for your excellent information you have got right
here on this post. I’ll be coming back to your website for more soon.
Nice blog here! Also your web site loads up
fast! What web host are you using? Can I get your affiliate link to your host?
I wish my web site loaded up as quickly as yours lol
You really make it appear so easy together with your
presentation but I to find this matter to be really one thing which I believe
I’d never understand. It kind of feels too complex and very huge
for me. I’m having a look forward in your subsequent submit,
I will attempt to get the cling of it!
You have observed very interesting details ! ps nice site.
I don’t even know how I ended up here, but I thought this post was
good. I don’t know who you are but certainly you are going to
a famous blogger if you aren’t already 😉 Cheers!
Hi there just wanted to give you a quick heads up and let you know
a few of the images 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 outcome.
Hello there! I simply want to offer you a huge thumbs up for your excellent info
you’ve got right here on this post. I’ll be returning to your website for more soon.
My coder is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the costs.
But he’s tryiong none the less. I’ve been using Movable-type on various websites
for about a year and am nervous about switching to another platform.
I have heard fantastic things about blogengine.net.
Is there a way I can transfer all my wordpress
posts into it? Any kind of help would be really appreciated!
Thanks for finally writing about >【BZOJ 4826】[HNOI2017] 影魔 – Qizy’s Database <Liked it!
Amazing! This blog looks exactly like my old one!
It’s on a totally different topic but it has pretty much
the same layout and design. Excellent choice of colors!
I visited several web pages however the audio quality for audio songs current at this website is genuinely excellent.
Your means of explaining all in this piece of writing is actually good, all be able to simply understand it, Thanks a lot.
Genuinely when someone doesn’t know after that its up to other people that they will
help, so here it occurs.
Hi there! 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 tips?
Definitely believe that which you said. Your favorite justification appeared to be on the net the easiest thing to be aware of. I say to you, I certainly get annoyed while people consider worries that they plainly do not know about. You managed to hit the nail upon the top and also defined out the whole thing without having side-effects , people could take a signal. Will likely be back to get more. Thanks