题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3238
离线版题目：http://paste.ubuntu.com/18084975/
数据生成器：http://paste.ubuntu.com/16074559/
这个东西，想了想，不会做QAQ于是可耻地看题解，果断SA算贡献
最近在做专题，又看到这个题，发现SAM算贡献不是更好算吗QAQ
贴一个SA的代码吧！SAM就偷懒不写啦！o(￣▽￣)ブ
#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
#define SA Suffix_Array
using namespace std;
const int MAXN = 1000000+9;
namespace Suffix_Array{
int sa[MAXN],bot[MAXN],t1[MAXN],t2[MAXN],height[MAXN],*rank,*tmp;
int n,m;
inline void build(char *s){
n = strlen(s+1); m = 26;
rank = t1; tmp = t2;
for (int i=1;i<=n;i++) bot[tmp[i]=s[i]-'a'+1]++;
for (int i=2;i<=m;i++) bot[i] += bot[i-1];
for (int i=1;i<=n;i++) sa[bot[tmp[i]]--] = i;
rank[sa[1]] = m = 1;
for (int i=2;i<=n;i++) rank[sa[i]] = s[sa[i]]==s[sa[i-1]]?m:++m;
for (int k=1;k<=n;k*=2){
int tot = 0;
for (int i=1;i<=m;i++) bot[i] = 0;
for (int i=n-k+1;i<=n;i++) tmp[++tot] = i;
for (int i=1;i<=n;i++) if (sa[i] > k) tmp[++tot] = sa[i] - k;
for (int i=1;i<=n;i++) bot[rank[i]]++;
for (int i=2;i<=m;i++) bot[i] += bot[i-1];
for (int i=n;i;i--) sa[bot[rank[tmp[i]]]--] = tmp[i];
swap(rank, tmp); rank[sa[1]] = m = 1;
for (int i=2;i<=n;i++) if (tmp[sa[i]] == tmp[sa[i-1]] && tmp[sa[i]+k] == tmp[sa[i-1]+k]) rank[sa[i]] = m; else rank[sa[i]] = ++m; if (m >= n) break;
}
}
inline void GetHeight(char *s){
for (int i=1;i<=n;i++) if (rank[i] > 1) {
int sta = max(0, height[rank[i-1]]-2);
int p1 = i+sta, p2 = sa[rank[i]-1]+sta;
while (s[p1++] == s[p2++]) sta++;
height[rank[i]] = sta;
}
}
};
int L[MAXN],R[MAXN]; LL vout;
int cnt,que[MAXN],pos[MAXN];
inline void GetAns(){
using namespace Suffix_Array;
for(int i=1;i<=n;i++) vout += (LL)i*(LL)(n-1);
cnt = 0;
for (int i=1;i<=n;i++){ while (cnt && que[cnt] >= height[i]) cnt--;
L[i] = pos[cnt]+1;
que[++cnt] = height[i]; pos[cnt] = i;
}
cnt = 0; pos[0] = n+1;
for (int i=n;i;i--){
while (cnt && que[cnt] > height[i]) cnt--;
R[i] = pos[cnt]-1;
que[++cnt] = height[i]; pos[cnt] = i;
}
for (int i=1;i<=n;i++) vout -= 2LL*(LL)(i-L[i]+1)*(LL)(R[i]-i+1)*(LL)height[i];
printf("%lld",vout);
}
char pat[MAXN];
int main(){
scanf("%s",pat+1);
SA::build(pat);
SA::GetHeight(pat);
GetAns();
return 0;
}
Way cool! Some very valid points! I appreciate you writing this write-up and also the rest of the site is really good.
I could not resist commenting. Perfectly written!
I enjoy what you guys are up too. This type of clever work and reporting!
Keep up the excellent works guys I’ve incorporated
you guys to my own blogroll.
Good day! This is kind of off topic but I need some help from an established blog.
Is it tough to set up your own blog? I’m not very techincal but
I can figure things out pretty quick. I’m thinking about setting up my own but I’m not sure where to start.
Do you have any points or suggestions? Thanks
Hello i am kavin, its my first time to commenting anyplace,
when i read this article i thought i could also make comment due to this brilliant piece of writing.
I’m impressed, I have to admit. Seldom do I come across a blog that’s both educative and amusing, and without a doubt, you have hit the nail on the head.
The issue is something which too few folks are speaking intelligently about.
I am very happy that I came across this in my search for something
relating to this.
My coder is trying to persuade 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 WordPress
on a number of websites for about a year and am nervous about
switching to another platform. I have heard good things about blogengine.net.
Is there a way I can import all my wordpress content into it?
Any help would be really appreciated!
It’s enormous that you are getting thoughts from this
piece of writing as well as from our dialogue made at this time.
Hi mates, good post and fastidious arguments
commented at this place, I am truly enjoying by these.
Hi there, i read your blog occasionally and i own a similar one and i was just curious if
you get a lot of spam responses? If so how do you protect against it, any plugin or anything you can advise?
I get so much lately it’s driving me crazy so any help is very much appreciated.
Hi everyone, it’s my first go to see at this web page, and piece of writing is truly fruitful
designed for me, keep up posting these types of articles.
I used to be able to find good information from your blog articles.
Hey there! I’ve been following your weblog for a long time now
and finally got the bravery to go ahead and give you a shout out from Kingwood
Tx! Just wanted to mention keep up the good job!
Hi there to every body, it’s my first visit of this blog; this web site includes
remarkable and actually excellent stuff designed for
readers.
I like looking through a post that will make men and women think.
Also, thank you for allowing for me to comment!
natalielise pof
Hi, I desire to subscribe for this webpage to get latest updates, thus where can i do it please assist.
Hi there, its good paragraph regarding media print, we
all know media is a impressive source of data.
I am in fact happy to read this webpage posts which consists of lots
of helpful facts, thanks for providing such
data.
What’s Happening i’m new to this, I stumbled upon this I’ve discovered It absolutely
helpful and it has aided me out loads. I hope to give a
contribution & aid different customers like its aided me.
Good job.
Greetings from Ohio! I’m bored to tears at work so I decided to check out your site on my iphone during
lunch break. I love the info you present here and can’t wait to take a
look when I get home. I’m surprised at how fast your blog loaded on my phone ..
I’m not even using WIFI, just 3G .. Anyways, amazing site!
Thanks for finally writing about >【BZOJ 3238】[AHOI2013] 差异 – Qizy’s Database <Liked it!
Excellent beat ! I wish to apprentice whilst you amend your site, how could
i subscribe for a blog site? The account aided me a acceptable deal.
I were tiny bit familiar of this your broadcast provided brilliant transparent concept natalielise plenty of fish
Wonderful blog! Do you have any tips for
aspiring writers? I’m hoping to start my own blog soon but I’m a little lost on everything.
Would you propose starting with a free platform like WordPress or go for a paid option? There are so many
options out there that I’m completely overwhelmed ..
Any tips? Bless you!
Hi! Someone in my Myspace group shared this site with
us so I came to take a look. I’m definitely enjoying the information. I’m bookmarking and will be tweeting this to my
followers! Great blog and terrific design and style.
Thank you for any other informative website. The place else may just I get that kind of
info written in such an ideal method? I have a undertaking that I am just now working on, and I’ve been at the
glance out for such information.
Its such as you learn my thoughts! You appear to
know a lot about this, like you wrote the e book in it or
something. I believe that you could do with
some p.c. to drive the message house a little bit, however
instead of that, this is fantastic blog. An excellent read.
I will definitely be back.
Hello there I am so happy I found your blog, I really found
you by accident, while I was browsing on Aol for something else,
Anyways I am here now and would just like to say many
thanks for a marvelous post and a all round entertaining blog (I also love
the theme/design), I don’t have time to read 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 great job.
I read this piece of writing fully on the topic of the
resemblance of most recent and earlier technologies, it’s amazing article.
Write more, thats all I have to say. Literally, it seems as
though you relied on the video to make your point.
You clearly know what youre talking about, why throw away your intelligence on just posting videos to your weblog when you could be giving us something enlightening to
read?
This is the right web site for anyone who wishes to find out about this topic.
You understand a whole lot its almost hard to argue with you (not that I personally would want to…HaHa).
You certainly put a new spin on a subject that has been written about for a long time.
Great stuff, just great!
Hurrah! After all I got a weblog from where I know how to genuinely take
helpful information concerning my study and knowledge.
Great blog you have here but I was wondering if you knew of
any message boards that cover the same topics talked about here?
I’d really like to be a part of group where I can get feed-back from other knowledgeable individuals that share the same interest.
If you have any recommendations, please let me know.
Thanks a lot!
Hey! Do you know if they make any plugins to help with Search Engine Optimization?
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. Appreciate it!
Just wish to say your article is as astonishing. The clarity in your post is just excellent and i can assume you are an expert on this
subject. Well with your permission let me to grab your feed to keep updated
with forthcoming post. Thanks a million and please continue the
gratifying work.
It is the best time to make a few plans for the future and it’s
time to be happy. I have read this post and if I may I want to counsel
you some interesting things or advice. Maybe you can write next articles referring to
this article. I want to read more issues about it!
Hi there it’s me, I am also visiting this web site daily, this site is really nice and the people are actually sharing fastidious thoughts.
This is the right blog for everyone who hopes to find out about this topic.
You understand a whole lot its almost hard to argue with
you (not that I actually will need to…HaHa). You definitely put a brand new
spin on a subject that’s been written about for decades.
Excellent stuff, just wonderful!
I pay a quick visit daily some websites and websites to read articles or
reviews, except this webpage offers feature based content.
Hola! I’ve been following your weblog for
a while now and finally got the courage to go ahead and give you a shout out from
Humble Tx! Just wanted to tell you keep up the great job!
Currently it looks like Expression Engine is the top blogging platform available right now.
(from what I’ve read) Is that what you are using on your
blog?
I’ve been exploring for a little for any high-quality articles or weblog posts in this sort of space .
Exploring in Yahoo I at last stumbled upon this site.
Studying this information So i’m satisfied to convey that I’ve a very excellent uncanny feeling I came upon exactly what I needed.
I so much surely will make certain to don?t forget
this website and provides it a glance regularly.
Nice blog here! Also your web site loads up very fast! What host are you using?
Can I get your affiliate link to your host?
I wish my site loaded up as quickly as yours lol
What i don’t realize is in reality how you are not actually a lot more neatly-liked than you might be
right now. You’re very intelligent. You recognize thus significantly in the case of this subject,
made me in my view consider it from numerous varied angles.
Its like women and men are not fascinated except it’s one thing to accomplish with Lady gaga!
Your own stuffs nice. All the time take care of it up!
My spouse and I stumbled over here coming from a different web page and thought
I might as well check things out. I like what I see so i am
just following you. Look forward to looking into your
web page yet again.
I was excited to discover this web site. I want to to thank
you for ones time for this wonderful read!!
I definitely enjoyed every bit of it and i also
have you book-marked to see new things in your blog.
Very good post! We will be linking to this particularly great article on our
website. Keep up the good writing.
Nice post. I learn something totally new and challenging on blogs I stumbleupon every day.
It will always be helpful to read through articles from other
authors and use something from other websites.
Fantastic website you have here but I was wanting to know if you knew of any message boards
that cover the same topics discussed in this article?
I’d really love to be a part of community where I can get responses from other knowledgeable people
that share the same interest. If you have any recommendations, please
let me know. Appreciate it!
I must thank you for the efforts you have put in writing
this blog. I am hoping to see the same high-grade
content by you in the future as well. In truth, your creative writing
abilities has motivated me to get my very own site now 😉
It’s hard to find experienced people in this particular subject, but you sound like you know what you’re talking about!
Thanks
Because the admin of this web site is working, no uncertainty very rapidly it
will be famous, due to its feature contents.
Hey there, You have done an excellent job. I’ll certainly digg it and personally recommend to my friends.
I’m confident they’ll be benefited from this web site.
It’s really a cool and useful piece of info. I am happy that
you just shared this useful information with us.
Please keep us informed like this. Thanks for sharing.
I do not even know how I ended up here, but I thought this post was
great. I do not know who you are but certainly you are going to a famous blogger
if you aren’t already 😉 Cheers!
Hey very nice blog!
Greetings! Very useful advice within this post!
It is the little changes that produce the greatest changes.
Thanks for sharing!
Wow, wonderful weblog format! How lengthy have you ever been running a blog for?
you make blogging glance easy. The overall look of your website is
magnificent, let alone the content!
always i used to read smaller articles or reviews that
as well clear their motive, and that is also happening with this paragraph which I am reading now.
I do consider all the ideas you have introduced
for your post. They are really convincing and will definitely work.
Nonetheless, the posts are too quick for beginners.
Could you please prolong them a little from next time?
Thanks for the post.
Thanks in favor of sharing such a pleasant thinking, article is good, thats why i have read
it completely
Hello I am so glad I found your weblog, I really found
you by accident, while I was looking on Yahoo for something else,
Regardless I am here now and would just like to say kudos for a marvelous post and a all round entertaining
blog (I also love the theme/design), I don’t have time to look over it all at the moment but I
have saved it and also added in your RSS feeds,
so when I have time I will be back to read more, Please do
keep up the great job.
Hello! I understand this is sort of off-topic however I needed to
ask. Does building a well-established website such as yours require a large amount
of work? I’m brand new to writing a blog but I do write in my diary everyday.
I’d like to start a blog so I can easily share my
experience and thoughts online. Please let me know if you have any kind of ideas or tips for brand new aspiring blog owners.
Appreciate it!
My relatives all the time say that I am wasting my time
here at net, however I know I am getting experience daily by reading thes nice content.
Hello to all, how is everything, I think every one is getting
more from this site, and your views are pleasant in support of
new people.
I know this website provides quality depending articles and other data, is there any other site which
gives these kinds of data in quality?
Hello! I’ve been reading your website for a long time now and finally
got the courage to go ahead and give you a shout out from Porter
Texas! Just wanted to mention keep up the great work!
I’ve been exploring for a little for any high quality articles or blog posts in this kind
of space . Exploring in Yahoo I ultimately stumbled upon this website.
Reading this information So i am happy to exhibit that I have a very good uncanny feeling I came upon exactly what
I needed. I so much without a doubt will make sure to don?t forget
this site and give it a look on a relentless basis.
An interesting discussion is definitely worth comment.
There’s no doubt that that you should publish more on this subject matter, it may not be a taboo
subject but usually people don’t speak about such issues.
To the next! Cheers!!
I am not sure where you are getting your info, but great
topic. I needs to spend some time learning more or understanding more.
Thanks for fantastic info I was looking for this information for
my mission.
Hey very interesting blog!
Exceptional post but I was wanting to know if you could write a litte more on this topic?
I’d be very grateful if you could elaborate a
little bit more. Thanks!
Wohh exactly what I was searching for, appreciate it for putting up.
It’s very effortless to find out any topic on net as compared to textbooks, as
I found this post at this web site.
You could definitely see your skills within the work you write.
The world hopes for more passionate writers such as you who aren’t afraid to mention how they believe.
At all times follow your heart.
This is really interesting, You are a very skilled blogger.
I have joined your feed and look forward to seeking more of your magnificent post.
Also, I have shared your website in my social networks!
Wow! This blog looks just like my old one! It’s on a totally different subject but it has pretty much the same layout
and design. Great choice of colors!
Hi there! I could have sworn I’ve been to
this blog before but after checking through some of the post I realized it’s new to me.
Anyhow, I’m definitely glad I found it and I’ll be book-marking and checking back frequently!
Oh my goodness! Awesome article dude! Thank you, However I am going through troubles with your RSS.
I don’t know why I cannot join it. Is there anybody having similar RSS problems?
Anyone that knows the answer can you kindly respond?
Thanks!!
Good post. I am dealing with many of these issues as well..
Whats up this is kinda 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 advice from someone with experience.
Any help would be enormously appreciated!
That is a great tip particularly to those fresh to the blogosphere.
Brief but very accurate info… Many thanks for sharing this one.
A must read post!
It is perfect time to make some plans for the future and it is time to be happy.
I have read this post and if I could I wish to suggest you few interesting things or tips.
Perhaps you can write next articles referring to this article.
I desire to read more things about it!
I think the admin of this site is actually working hard for his site,
since here every data is quality based stuff.
I like the helpful information you provide in your articles. I will bookmark your weblog and check again here frequently. I’m quite certain I’ll learn many new stuff right here! Best of luck for the next!
This is one awesome article post.Much thanks again. Much obliged.
Thank you ever so for you article post.Really thank you! Cool.