相关链接
题目传送门: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; }
Wonderful, what a blog it is! This blog provides
useful facts to us, keep it up.
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!
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!
When some one searches for his essential thing, therefore
he/she wants to be available that in detail, so that thing is maintained
over here.
My brother recommended I would possibly like this web site.
He was totally right. This submit actually made my day.
You can not consider just how much time I had spent for this information!
Thank you!
I read this article completely about the resemblance of
most recent and preceding technologies, it’s remarkable article.
Your style is unique in comparison to other folks I have
read stuff from. Many thanks for posting when you have the opportunity, Guess I will just
bookmark this page.
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
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!
Keep on working, great job!
This is a topic that’s near to my heart… Thank you!
Where are your contact details though?
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..
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.
It’s actually a nice and useful piece of info. I’m satisfied that you
just shared this useful info with us. Please keep us informed
like this. Thanks for sharing.
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.
Wow, that’s what I was looking for, what a material!
existing here at this webpage, thanks admin of this website.
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.
I think this is one of the most significant info for
me. And i’m glad reading your article. But should remark on some general things, The website style is perfect, the articles is really nice : D.
Good job, cheers
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.
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
Greetings! Very useful advice within this article! It is the little changes that
produce the largest changes. Many thanks for sharing!
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!
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!
Hey there! Would you mind if I share your blog with my facebook group?
There’s a lot of folks that I think would really appreciate your content.
Please let me know. Many thanks
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.
Rattling clean internet site, thanks for this post.
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.
I am thinking of creating ebook of articles that are not copyrighted.. How , where can I go to get it?.
I have a blogspot page, How can I traffic the vistors and get their ip address?