【BZOJ 4278】[ONTAK2015] Tasowanie

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4278

解题报告

考虑归并排序
唯一麻烦的地方就是两个字符相同时选哪个
我们可以比较后缀的字典序来解决这个问题
具体实现上,我们可以使用SA

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 800009;
const int SGZ = 1001;

int n, m, s[N];
class Suffix_Array{
int *rk, *tmp, sa[N], bot[N], arr1[N], arr2[N], que[N];
public:
	inline void build(int *s, int nn) {
		rk = arr1; tmp = arr2; int sgz = SGZ;
		for (int i = 1; i <= nn; i++) bot[s[i]]++;
		for (int i = 1; i <= sgz; i++) bot[i] += bot[i - 1];
		for (int i = 1; i <= nn; i++) que[bot[s[i]]--] = i;
		rk[que[1]] = sgz = 1; 
		for (int i = 2; i <= nn; i++) rk[que[i]] = (sgz += s[que[i]] != s[que[i - 1]]);
		for (int l = 1; l < nn && sgz < nn; l <<= 1) {
			int tt = 0;
			for (int i = nn - l + 1; i <= nn; i++) tmp[++tt] = i;
			for (int i = 1; i <= nn; i++) if (que[i] > l) tmp[++tt] = que[i] - l;
			for (int i = 0; i <= sgz; i++) bot[i] = 0;
			for (int i = 1; i <= nn; i++) bot[rk[i]]++;
			for (int i = 1; i <= sgz; i++) bot[i] += bot[i - 1];
			for (int i = nn; i; i--) que[bot[rk[tmp[i]]]--] = tmp[i];
			swap(rk, tmp); rk[que[1]] = sgz = 1;
			for (int i = 2; i <= nn; i++) {
				rk[que[i]] = (sgz += tmp[que[i]] != tmp[que[i - 1]] || tmp[que[i] + l] != tmp[que[i - 1] + l]);
			}
		}
	}
	inline int rank(int p) {
		return rk[p];		
	}
}sa;

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;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		s[i] = read();
	}
	s[n + 1] = 1001;
	m = read();
	for (int i = 1; i <= m; i++) {
		s[i + n + 1] = read();
	}
	sa.build(s, n + m + 1);
	for (int i = 1, j = 1, k = 1; k <= n + m; k++) {
		if (i <= n && j <= m) {
			if (s[i] < s[j + n + 1] || (s[i] == s[j + n + 1] && sa.rank(i) < sa.rank(j + n + 1))) {
				printf("%d ", s[i++]);
			} else {
				printf("%d ", s[n + 1 + j++]);
			}
		} else if (i <= n) {
			printf("%d ", s[i++]);
		} else {
			printf("%d ", s[n + 1 + j++]);
		}
	}
	return 0;
}

29 thoughts to “【BZOJ 4278】[ONTAK2015] Tasowanie”

  1. This design is wicked! You most certainly 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!) Excellent job.

    I really enjoyed what you had to say, and more than that, how you presented
    it. Too cool!

  2. When I initially left a comment I seem to have clicked the -Notify me
    when new comments are added- checkbox and now every time a comment is added
    I get 4 emails with the exact same comment. There
    has to be a way you are able to remove me from that service?
    Thanks a lot!

  3. Great blog here! Also your 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

  4. Hello! I could have sworn I’ve been to this blog before but after browsing through some of the post I realized it’s new to me. Anyways, I’m definitely happy I found it and I’ll be book-marking and checking back frequently!

  5. I am extremely impressed with your writing skills and also with the structure for your
    blog. Is this a paid theme or did you customize it
    yourself? Anyway keep up the nice quality writing, it’s uncommon to look a great
    blog like this one today..

  6. Just wish to say your article is as astonishing. The clarity on your post is just nice and that i can assume you are
    an expert in this subject. Well along with your permission let me to grab your feed to stay updated with impending post.
    Thank you one million and please carry on the rewarding work.

  7. Hmm it looks like your site ate my first comment
    (it was extremely long) so I guess I’ll just sum it up what I had written and say,
    I’m thoroughly enjoying your blog. I as well am an aspiring blog writer but I’m still new to everything.

    Do you have any suggestions for novice blog
    writers? I’d genuinely appreciate it.

  8. Good day! Do you use Twitter? I’d like to follow you if that would be okay.

    I’m absolutely enjoying your blog and look forward
    to new updates.

  9. Hello to all, for the reason that I am in fact keen of reading this webpage’s post to be updated regularly.
    It consists of pleasant material.

  10. I do not know whether it’s just me or if everybody
    else experiencing problems with your website. It appears like some of the text in your posts
    are running off the screen. Can someone else please comment and let me know if this is
    happening to them too? This could be a issue with
    my web browser because I’ve had this happen before.
    Kudos

  11. I’m truly enjoying the design and layout of your site.
    It’s a very easy on the eyes which makes it much
    more enjoyable for me to come here and visit more often. Did you hire out a developer
    to create your theme? Exceptional work!

  12. 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 Movable-type on various websites for about a
    year and am anxious 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!

  13. With havin so much content do you ever run into any problems of plagorism or copyright infringement?
    My website has a lot of exclusive content I’ve either created myself or outsourced but it looks like a lot of it is popping
    it up all over the web without my agreement. Do you know any methods to help stop content from being ripped off?
    I’d really appreciate it.

  14. An outstanding share! I’ve just forwarded this onto
    a colleague who was conducting a little homework on this.

    And he in fact bought me breakfast due to the fact that I stumbled upon it for him…
    lol. So allow me to reword this…. Thank YOU for the meal!!
    But yeah, thanks for spending time to discuss this matter here on your website.

发表评论

电子邮件地址不会被公开。 必填项已用*标注