【日常小测】回转寿司

Qizy Heap, Tricks, 分块, 数据结构, 解题报告

相关链接

题目传送门：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;
}

283 thoughts to “【日常小测】回转寿司”

  40. 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!

    Reply

  44. 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.

    Reply

  85. 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?

    Reply

  91. 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!

    Reply

  103. 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.

    Reply

  128. 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!

    Reply

  134. 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!

    Reply

  136. 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.

    Reply

  141. 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.

    Reply

  151. 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.

    Reply

  162. 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?

    Reply

  189. 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

    Reply

  193. 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!

    Reply

  195. 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.

    Reply

  238. 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?|

    Reply

  241. 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!|

    Reply

  244. 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.|

    Reply

  245. 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|

    Reply

  251. 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!|

    Reply

  257. 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!|

    Reply

  265. 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.|

    Reply

  269. 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.|

    Reply

  272. 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!|

    Reply

  281. 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?|

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *