相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/20170623_statement.pdf
解题报告
看到这题我们不难想到分块
更进一步,对于每一个块来说,块内的数的相对大小不变
于是我们只需要用堆便可维护块内有哪些数
再稍加观察,我们发现只要再用一个堆记录块内的操作,然后从左向右扫一遍便可更新具体的数
于是我们就可以在:$O(n^{1.5} \log n)$的时间复杂度内解决这个问题了
另外priority_queue
的构造函数是$O(n)$的
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 400009; const int M = 25009; const int S = 1000; const int B = N / S + 10; int n, sn, m, arr[N]; priority_queue<int> val[B]; vector<int> opr[B]; 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 get_element(int w) { if (opr[w].empty()) { return; } priority_queue<int, vector<int>, greater<int> > heap(opr[w].begin(), opr[w].end()); for (int i = max(1, w * S), lim = min((w + 1) * S - 1, n); i <= lim; i++) { if (arr[i] > heap.top()) { heap.push(arr[i]); arr[i] = heap.top(); heap.pop(); } } opr[w].clear(); } inline int modify_element(int w, int s, int t, int v) { get_element(w); int tmp = -1; for (int i = s; i <= t; i++) { if (v < arr[i]) { tmp = arr[i]; swap(v, arr[i]); } } val[w] = priority_queue<int>(arr + max(1, w * S), arr + 1 + min(n, (w + 1) * S - 1)); return v; } inline int modify_block(int w, int v) { val[w].push(v); int ret = val[w].top(); val[w].pop(); if (v != ret) { opr[w].push_back(v); } return ret; } inline int solve(int s, int t, int v) { int ss = s / S, st = t / S; v = modify_element(ss, s, min(t, (ss + 1) * S - 1), v); if (ss != st) { for (int i = ss + 1; i < st; i++) { v = modify_block(i, v); } v = modify_element(st, st * S, t, v); } return v; } int main() { n = read(); m = read(); sn = n / S; for (int i = 1; i <= n; i++) { arr[i] = read(); } for (int i = 0; i <= sn; i++) { val[i] = priority_queue<int>(arr + max(1, i * S), arr + 1 + min(n, (i + 1) * S - 1)); } for (int tt = 1; tt <= m; tt++) { int s = read(), t = read(), v = read(); if (s <= t) { v = solve(s, t, v); } else { v = solve(s, n, v); v = solve(1, t, v); } printf("%d\n", v); } return 0; }
I really liked your blog article. Cool.
Thanks for the blog article.Thanks Again. Will read on…
Thanks-a-mundo for the article. Want more.
Very good blog.Really looking forward to read more. Really Cool.
A big thank you for your blog post.Thanks Again. Cool.
Thanks for sharing, this is a fantastic blog.Thanks Again.
Thanks for the blog.Much thanks again. Great.
Thanks-a-mundo for the article.Much thanks again. Keep writing.
wow, awesome blog article.Really looking forward to read more. Fantastic.
Appreciate you sharing, great article post.Much thanks again. Fantastic.
Im obliged for the blog article.Much thanks again. Want more.
Awesome blog post.Really looking forward to read more. Keep writing.
Fantastic article post.Really thank you! Really Great.
Appreciate you sharing, great article post.Really looking forward to read more. Cool.
Thanks a lot for the article post.Really thank you! Really Great.
I really liked your article.Really thank you! Really Cool.
Im grateful for the post.Thanks Again. Want more.
I cannot thank you enough for the article post.Really looking forward to read more. Cool.
Really enjoyed this blog post.Really looking forward to read more. Will read on…
Awesome post.Thanks Again.
Very informative post.Really looking forward to read more. Really Great.
I think this is a real great article post.Much thanks again. Really Cool.
Really enjoyed this blog post.Thanks Again. Cool.
Thank you ever so for you post.Really looking forward to read more. Fantastic.
Thanks for sharing, this is a fantastic blog article.Really thank you! Really Great.
Really appreciate you sharing this post.Really thank you! Will read on…
Thank you ever so for you post.Much thanks again. Great.
Very neat blog article. Will read on…
Fantastic blog post.Really thank you! Really Cool.
Really appreciate you sharing this article post.Really thank you! Awesome.
I think this is a real great post.Much thanks again. Cool.
Thank you ever so for you blog post. Want more.
I appreciate you sharing this article post.Thanks Again. Great.
I really liked your article.Thanks Again. Cool.
I really enjoy the post.Really looking forward to read more. Much obliged.
I truly appreciate this post.Really thank you! Cool.
I cannot thank you enough for the blog post.Really thank you! Great.
Appreciate you sharing, great blog post.Thanks Again. Keep writing.
Enjoyed every bit of your blog article. Great.
Hello this is kind of of off topic but I was
wanting to know if blogs use WYSIWYG editors or if
you have to manually code with HTML. I’m starting a blog soon but have no coding experience so I wanted to
get guidance from someone with experience. Any help would be greatly appreciated!
Great article.
I really like and appreciate your blog.Thanks Again. Keep writing.
Looking forward to reading more. Great blog post. Really thank 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 could do with some pics
to drive the message home a bit, but other than that, this is excellent blog.
An excellent read. I’ll certainly be back.
Appreciate you sharing, great blog article.Really looking forward to read more. Will read on…
Looking forward to reading more. Great blog article. Keep writing.
It is truly a nice and useful piece of info.
I am happy that you just shared this useful information with us.
Please stay us informed like this. Thanks for sharing.
I really liked your article post.Thanks Again. Will read on…
A big thank you for your blog. Keep writing.
Hey, thanks for the article.Really thank you!
Hey, thanks for the blog. Keep writing.
It’s remarkable in support of me to have a web page, which is helpful in support of my experience.
thanks admin
Wow, great blog article. Really Cool.
I loved your blog post.Thanks Again. Cool.
Major thankies for the blog post.Really thank you! Much obliged.
Therefore that as why this piece of writing is perfect. Thanks!
Appreciation to my father who stated to me concerning this blog, this
blog is in fact remarkable.
Enjoyed every bit of your blog.Really thank you! Really Cool.
Thank you for your article.Really thank you! Really Cool.
Thank you ever so for you article.Really thank you! Awesome.
Keep this going please, great job!
Thank you ever so for you blog article.Really looking forward to read more. Will read on…
Awesome blog.Much thanks again. Cool.
Thank you for your blog article.Much thanks again. Fantastic.
Great post. Want more.
What’s up, constantly i used to check webpage posts here early in the morning, as i love to find out more and more.
Say, you got a nice article post. Much obliged.
Great blog.Thanks Again. Keep writing.
I really liked your blog post. Thanks Again. Really Cool.
Very informative article post.Thanks Again. Much obliged.
Great blog article.Really looking forward to read more.
Major thanks for the article. Fantastic.
Major thanks for the blog post.Really looking forward to read more. Fantastic.
I think this is a real great blog post.Much thanks again. Cool.
Looking forward to reading more. Great post.Much thanks again. Fantastic.
Great, thanks for sharing this blog post.Really thank you! Cool.
Really appreciate you sharing this blog article. Keep writing.
Thanks so much for the blog post.Really looking forward to read more. Will read on…
Muchos Gracias for your blog post.Really thank you! Much obliged.
I really like and appreciate your blog.Much thanks again. Cool.
A round of applause for your article post.Really looking forward to read more. Awesome.
It’s in fact very complex in this busy life to listen news on TV, thus I just use web for that reason, and obtain the newest information.
Thank you for your article post.Thanks Again. Great.
Muchos Gracias for your blog article.Much thanks again. Will read on…
Tremendous issues here. I’m very satisfied to look your article.
Thank you a lot and I am looking ahead to contact you.
Will you kindly drop me a mail?
Pretty! This was an incredibly wonderful post. Thank
you for supplying this info.
I really like and appreciate your article post.Really thank you! Really Great.
Very good post. Great.
Thanks for sharing, this is a fantastic article post. Want more.
Thanks for the blog post. Really Cool.
My developer is trying to persuade me to move to .net from PHP.
I have always disliked the idea because of the expenses.
But he’s tryiong none the less. I’ve been using WordPress on numerous websites for about a year and am
worried about switching to another platform. I have heard
good things about blogengine.net. Is there a way I can transfer all my wordpress content into it?
Any kind of help would be greatly appreciated!
I really like and appreciate your post.Really thank you! Really Great.
Very informative post.Really thank you! Fantastic.
I appreciate you sharing this article post.
Im thankful for the article post. Keep writing.
Really informative post.Thanks Again. Cool.
Looking forward to reading more. Great blog post.Thanks Again. Much obliged.
Muchos Gracias for your article post.Really thank you! Keep writing.
I really liked your blog article.Really thank you!
Great blog.Thanks Again. Cool.
Great blog article.Really looking forward to read more. Really Great.
I really liked your post.Really looking forward to read more.
I’ll right away seize your rss as I can not to find your e-mail subscription hyperlink or newsletter service. Do you’ve any? Please allow me understand in order that I could subscribe. Thanks.
Very informative post. Fantastic.
Really appreciate you sharing this blog post.Thanks Again. Much obliged.
Im obliged for the blog article.Thanks Again. Much obliged.
Im grateful for the blog post.Really thank you! Keep writing.
Im grateful for the blog article.Much thanks again. Great.
Thank you for your blog.Really looking forward to read more. Really Cool.
I appreciate you sharing this blog article.Much thanks again. Keep writing.
Enjoyed every bit of your blog article. Really Cool.
Really enjoyed this article.Thanks Again. Great.
Major thanks for the article post.Thanks Again. Great.
Thanks for the post admin, I love your website.
Im grateful for the post.Really looking forward to read more.
Thanks-a-mundo for the article.Really thank you! Really Cool.
I truly appreciate this article.Thanks Again. Awesome.
Say, you got a nice blog article.Really looking forward to read more. Awesome.
Im grateful for the article post.Thanks Again. Really Great.
Really informative article.Really looking forward to read more. Awesome.
A big thank you for your article.Thanks Again. Much obliged.
Appreciate you sharing, great blog article.Much thanks again. Much obliged.
Awesome article post.Really looking forward to read more. Fantastic.
I appreciate you sharing this blog article.Much thanks again. Keep writing.
I truly appreciate this blog post.Really thank you! Really Cool.
Major thanks for the blog post. Much obliged.
This is one awesome article. Really Great.
You’re so interesting! I do not believe I have read a single thing like that before.
So great to find someone with a few unique thoughts on this subject.
Really.. thanks for starting this up. This site is one thing that is required on the web, someone with a bit of originality!
Really appreciate you sharing this article.Really thank you!
I really like and appreciate your article.Thanks Again.
Great, thanks for sharing this article post. Really Cool.
A big thank you for your blog.Really thank you! Really Cool.
Thanks so much for the article.Really thank you!
It’s perfect time to make some plans for the future and
it’s time to be happy. I have read this post and if I could
I wish to suggest you some interesting things or suggestions.
Maybe you can write next articles referring to this article.
I desire to read even more things about it!
A round of applause for your article.Much thanks again. Awesome.
Attractive section of content. I just stumbled
upon your site and in accession capital to claim that I get
actually loved account your blog posts. Anyway I will be subscribing on your augment or even I success you access persistently quickly.
Im thankful for the blog article.Really thank you! Great.
I truly appreciate this blog post.Really looking forward to read more.
Really enjoyed this post.Thanks Again. Fantastic.
Very neat blog post.Thanks Again. Cool.
Attractive section of content. I just stumbled upon your blog and
in accession capital to assert that I acquire actually enjoyed account your blog
posts. Anyway I will be subscribing to your augment and even I
achievement you access consistently fast.
Im thankful for the post.Much thanks again. Fantastic.
Looking forward to reading more. Great blog post.Thanks Again. Really Great.
Great, thanks for sharing this blog post.Much thanks again. Really Cool.
Great blog article. Will read on…
Thanks a lot for the article post. Much obliged.
Thanks for sharing, this is a fantastic blog post.Really thank you! Keep writing.
Awesome article post.Really thank you! Fantastic.
Hey, thanks for the article post.Thanks Again. Cool.
Really appreciate you sharing this blog.Thanks Again. Awesome.
I’m amazed, I have to admit. Seldom do I encounter a blog that’s equally educative and interesting, and without a doubt, you’ve hit the nail on the head.
The issue is something too few men and women are speaking intelligently about.
Now i’m very happy that I came across this in my search
for something regarding this.
Really appreciate you sharing this blog post.Thanks Again.
I loved your article.Much thanks again. Keep writing.
Muchos Gracias for your blog article.Really looking forward to read more. Really Cool.
I cannot thank you enough for the post.Really looking forward to read more. Great.
Very neat blog article.Thanks Again. Cool.
I really like and appreciate your blog.Really looking forward to read more. Want more.
I cannot thank you enough for the blog article.Really looking forward to read more. Great.
Thanks again for the article post. Want more.
I cannot thank you enough for the blog article.Much thanks again. Really Cool.
Major thanks for the blog post.Really thank you! Really Great.
Right now it sounds like BlogEngine is the best blogging platform out
there right now. (from what I’ve read) Is that what you’re using on your blog?
A big thank you for your blog article.Really thank you! Will read on…
Im thankful for the blog article.Really looking forward to read more. Keep writing.
Thanks a lot for the blog article.Thanks Again. Will read on…
Very informative blog article.Really thank you! Awesome.
I am so grateful for your blog post.Much thanks again. Cool.
Thanks again for the post.Really thank you! Will read on…
Thanks-a-mundo for the post.Thanks Again.
I appreciate you sharing this blog article.Really thank you! Want more.
wow, awesome blog post.Really looking forward to read more. Really Great.
I am so grateful for your article post.Much thanks again. Will read on…
It’s hard to find educated people in this particular topic, however, you sound like you know what you’re talking about!
Thanks
Its not my first time to pay a visit this web site, i am visiting this web page dailly
and take good information from here all the time.
Muchos Gracias for your article post.Really thank you! Much obliged.
wow, awesome blog post.Much thanks again.
Thanks-a-mundo for the blog article.Really looking forward to read more.
Really enjoyed this post.Thanks Again. Really Great.
I like reading through a post that can make people think.
Also, thanks for allowing for me to comment!
Really appreciate you sharing this article post.Much thanks again. Awesome.
Very informative blog post.Thanks Again. Will read on…
Wow, great article.Much thanks again. Will read on…
Wow, great article.Much thanks again.
This is one awesome post.Really thank you! Will read on…
Say, you got a nice blog article. Great.
Really appreciate you sharing this article. Cool.
Major thanks for the article post.Really thank you! Really Great.
Thanks so much for the article post.Really looking forward to read more.
I get pleasure from, result in I discovered exactly what I was taking
a look for. You have ended my four day lengthy hunt! God Bless you man. Have a nice day.
Bye
Wow, great blog post.Really thank you! Really Cool.
Major thanks for the article post.Much thanks again.
I value the blog.Thanks Again. Fantastic.
Heya outstanding website! Does running a blog like this take a
large amount of work? I have virtually no understanding of coding however I was hoping to
start my own blog soon. Anyhow, if you have any ideas
or techniques for new blog owners please share. I understand this
is off subject but I simply wanted to ask. Thanks a lot!
Really informative article post.Much thanks again. Great.
Hi I am so delighted I found your webpage, I really found you by error,
while I was researching on Bing for something else, Regardless I am here now
and would just like to say cheers for a incredible post and
a all round entertaining blog (I also love the theme/design), I don’t
have time to browse it all at the minute but I have saved it and
also included your RSS feeds, so when I have time I will be back to read more, Please
do keep up the awesome work.
Great blog article.Much thanks again. Keep writing.
wow, awesome blog post.
Great blog.Really thank you! Really Cool.
I loved your blog article. Much obliged.
Very good blog post.Really thank you! Great.
Thanks for sharing, this is a fantastic article. Fantastic.
Awesome blog.Thanks Again. Will read on…
Thanks for sharing, this is a fantastic article.Really thank you! Fantastic.
Really appreciate you sharing this article. Fantastic.
I am so grateful for your blog.Thanks Again.
Say, you got a nice blog. Fantastic.
I am so grateful for your article.Much thanks again. Much obliged.
I really like and appreciate your post.Thanks Again. Cool.
I value the blog article.Much thanks again. Fantastic.
I loved your article post.
Say, you got a nice article.Thanks Again. Awesome.
Awesome blog article.Really looking forward to read more. Really Great.
Really informative blog article.Really thank you! Will read on…
I value the article post. Cool.
Hey, thanks for the article.Really looking forward to read more. Cool.
Thanks a lot for the blog article.Really looking forward to read more. Will read on…
I really enjoy the article.Really thank you!
I value the post. Much obliged.
Very good article post.Really thank you! Really Great.
I don’t usually comment but I gotta state appreciate it for the post on this special one : D.
Im obliged for the article post.Thanks Again.
I loved your blog post.Really thank you! Really Great.
I appreciate you sharing this article.Thanks Again. Want more.
Im obliged for the post.Really looking forward to read more. Really Cool.
I loved your article post.Really looking forward to read more.
Say, you got a nice blog.Really thank you! Keep writing.
I cannot thank you enough for the post.Really thank you! Awesome.
Im thankful for the post.Much thanks again. Want more.
Awesome article. Much obliged.
Appreciate you sharing, great blog article. Much obliged.
Hey, thanks for the blog article. Will read on…
I think this is a real great article post.Much thanks again. Keep writing.
Great, thanks for sharing this blog article.Much thanks again. Cool.
Fantastic blog post.Really looking forward to read more. Fantastic.
A big thank you for your post.Really looking forward to read more. Will read on…
Hey, thanks for the article.Much thanks again. Really Great.
Great, thanks for sharing this blog post. Cool.
Hi! Do you know if they make any plugins to safeguard against hackers? I’m kinda paranoid about losing everything I’ve worked hard on. Any recommendations?|
Really informative post. Keep writing.
Fantastic blog post.Much thanks again. Awesome.
It is the best time to make a few plans for the longer term and it’s time to be happy. I have read this submit and if I could I want to suggest you some interesting issues or advice. Perhaps you can write next articles regarding this article. I wish to read more issues approximately it!|
Wow, great blog post.Much thanks again. Keep writing.
Hey, thanks for the article.Much thanks again. Awesome.
Aw, this was an incredibly nice post. Finding the time and actual effort to produce a really good article… but what can I say… I put things off a whole lot and never seem to get nearly anything done.|
I think this is one of the most vital info for me. And i am glad reading your article. But wanna remark on some general things, The web site style is great, the articles is really nice : D. Good job, cheers|
Very neat blog post.Really thank you!
Really informative blog.Really thank you! Really Great.
Hello, this weekend is good in favor of me, since this point in time i am reading this impressive educational article here at my house.|
Great post.Really thank you! Really Cool.
Major thankies for the blog article.Much thanks again. Really Cool.
First of all I want to say awesome blog! I had a quick question in which I’d like to ask if you do not mind. I was interested to know how you center yourself and clear your thoughts before writing. I’ve had a difficult time clearing my thoughts in getting my ideas out. I truly do take pleasure in writing but it just seems like the first 10 to 15 minutes are wasted simply just trying to figure out how to begin. Any recommendations or hints? Kudos!|
Really appreciate you sharing this article. Keep writing.
I am so grateful for your blog article.Thanks Again. Really Cool.
It’s appropriate time to make a few plans for the future and it’s time to be happy. I’ve learn this put up and if I may I want to recommend you some interesting things or tips. Maybe you can write subsequent articles referring to this article. I desire to learn more things about it!|
Really appreciate you sharing this post.Much thanks again. Much obliged.
Looking forward to reading more. Great article.Much thanks again. Really Cool.
Hi fantastic website! Does running a blog similar to this take a lot of work? I’ve absolutely no expertise in coding but I had been hoping to start my own blog in the near future. Anyhow, if you have any suggestions or techniques for new blog owners please share. I understand this is off subject nevertheless I simply wanted to ask. Cheers!|
Thanks for sharing, this is a fantastic article post.Thanks Again. Keep writing.
I truly appreciate this post.Really looking forward to read more. Want more.
No matter if some one searches for his essential thing, thus he/she needs to be available that in detail, thus that thing is maintained over here.|
I really enjoy the blog post.Thanks Again. Really Cool.
Wow, great blog post. Really Cool.
Hey, thanks for the blog article.Much thanks again. Fantastic.
It’s very effortless to find out any topic on net as compared to books, as I found this post at this web page.|
Excellent items from you, man. I’ve keep in mind your stuff previous to and you’re just extremely fantastic. I really like what you’ve acquired here, really like what you are saying and the way in which you are saying it. You make it entertaining and you continue to take care of to keep it wise. I cant wait to read far more from you. This is actually a great web site.|
Thanks for the good writeup. It in fact was a entertainment account it. Look complex to far delivered agreeable from you! However, how can we keep in touch?|
I loved your article.Really thank you! Great.
A round of applause for your article post.Really thank you! Fantastic.
Hello, i read your blog occasionally and i own a similar one and i was just wondering if you get a lot of spam remarks? If so how do you reduce it, any plugin or anything you can recommend? I get so much lately it’s driving me insane so any support is very much appreciated.|
Very neat article. Much obliged.
Thanks so much for the article.Thanks Again. Great.
The other day, while I was at work, my cousin stole my iPad and tested to see if it can survive a forty 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 completely off topic but I had to share it with someone!|
Really enjoyed this blog.Thanks Again. Keep writing.
Looking forward to reading more. Great article.Thanks Again. Much obliged.
This is one awesome article. Want more.
Wow, great blog article.Really thank you! Keep writing.
I every time used to read piece of writing in news papers but now as I am a user of web therefore from now I am using net for posts, thanks to web.|
Major thankies for the blog post.Thanks Again. Really Great.
Really informative post. Awesome.
Good day! Would you mind if I share your blog with my zynga group? There’s a lot of people that I think would really enjoy your content. Please let me know. Thanks|
I’m really enjoying the theme/design of your blog. Do you ever run into any web browser compatibility issues? A handful of my blog audience have complained about my blog not working correctly in Explorer but looks great in Safari. Do you have any advice to help fix this problem?|
If some one needs to be updated with most recent technologies after that he must be pay a visit this site and be up to date all the time.|
What’s up to all, since I am in fact eager of reading this website’s post to be updated daily. It consists of pleasant information.|