相关链接
题目传送门Ⅰ：http://uoj.ac/problem/131
题目传送门Ⅱ：http://www.lydsy.com/JudgeOnline/problem.php?id=4199
神犇题解：https://blog.sengxian.com/solutions/bzoj-4199
解题报告
其实sengxian都写了题解了，我还有什么写的意义 _(:з」∠)_
不过还是简单说两句吧！
我们考虑把SA建出来，height数组搞出来
然后把height数组排个序
从小到大依次合并上去就可以辣！
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 600009;
const LL INF = 1e18;
int n,val[N],sz[N],mx[N],mn[N];
int height[N],bot[N],sa[N],arr[N];
int *rak,*que,arr1[N],arr2[N],fa[N];
char pat[N]; LL ans1,ans2;
stack<pair<LL,LL> > ans;
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline bool cmp(const int &a, const int &b) {
return height[a] > height[b];
}
class Suffix_Array{
public:
inline void build() {
rak = arr1; que = arr2;
for (int i=1;i<=n;i++) bot[pat[i]-'a'+1]++;
for (int i=1;i<=26;i++) bot[i] += bot[i-1];
for (int i=1;i<=n;i++) sa[bot[pat[i]-'a'+1]--] = i;
for (int ty=0,i=1;i<=n;i++) rak[sa[i]] = pat[sa[i]]==pat[sa[i-1]]? ty: ++ty;
for (int l=1,tot=0,ty;l<n;l<<=1,tot=0) {
memset(bot,0,sizeof(bot));
for (int i=n-l+1;i<=n;i++) que[++tot] = i;
for (int i=1;i<=n;i++) if (sa[i]>l) que[++tot] = sa[i] - l;
for (int i=1;i<=n;i++) bot[rak[i]]++;
for (int i=1;i<=n;i++) bot[i] += bot[i-1];
for (int i=n;i;i--) sa[bot[rak[que[i]]]--] = que[i];
swap(rak, que); rak[sa[1]] = ty = 1; bot[1] = 1;
for (int i=2;i<=n;i++)
if (que[sa[i]] == que[sa[i-1]] && que[sa[i]+l] == que[sa[i-1]+l]) rak[sa[i]] = ty;
else bot[rak[sa[i]] = ++ty] = 0;
if (ty >= n) break;
}
Get_Height();
}
inline void solve() {
for (int i=1;i<=n;i++) {
arr[i] = fa[i] = i; sz[i] = 1;
mn[i] = mx[i] = val[sa[i]];
}
sort(arr+1, arr+1+n, cmp);
for (int i=n-1,j=1;~i;i--) {
for (;height[arr[j]]>=i;++j) update(arr[j]);
ans.push(make_pair(ans1, ans2));
}
for (;!ans.empty();ans.pop())
printf("%lld %lld\n",ans.top().first, ans.top().second);
}
private:
inline void Get_Height() {
for (int i=1,len,p1,p2;i<=n;i++) {
len = max(height[rak[i-1]] - 1, 0);
p1 = i + len; p2 = sa[rak[i]-1] + len;
while (pat[p1] == pat[p2]) ++p1, ++p2, ++len;
height[rak[i]] = len;
} height[1] = -1;
}
int find(int x) {return fa[x]==x?x:find(fa[x]);}
inline void update(int i) {
static int E = 1; if (E) E = 0, ans2 = -INF;
int f1 = find(i), f2 = find(i-1);
ans1 += (LL)sz[f1] * sz[f2];
ans2 = max(ans2, (LL)mx[f2] * mx[f1]);
ans2 = max(ans2, (LL)mn[f2] * mn[f1]);
sz[f1] += sz[f2]; fa[f2] = f1;
mx[f1] = max(mx[f1], mx[f2]);
mn[f1] = min(mn[f1], mn[f2]);
}
}SA;
int main() {
n = read();
scanf("%s",pat+1);
for (int i=1;i<=n;i++) val[i] = read();
SA.build();
SA.solve();
return 0;
}
—————————— UPD 2017.7.10 ——————————
显然这货用SAM也是可做的
Usually I don’t read post on blogs, however I would like to say that this write-up very forced me to take a look at and do it!
Your writing style has been surprised me. Thank you, quite great
post.
Whats up this is kind of of off topic but I was wondering if blogs use WYSIWYG editors or if
you have to manually code with HTML. I’m starting a blog soon but have no coding skills so I wanted to get guidance from someone with experience.
Any help would be greatly appreciated!
Ahaa, its good conversation about this paragraph at this place at this
weblog, I have read all that, so now me also commenting here.
I read this article completely regarding the resemblance of newest and earlier technologies,
it’s awesome article.
Hmm it looks like your blog ate my first comment
(it was super long) so I guess I’ll just sum it up what I submitted and say, I’m
thoroughly enjoying your blog. I too am an aspiring blog writer but I’m still new to everything.
Do you have any tips for inexperienced blog writers?
I’d certainly appreciate it.
I’m truly enjoying the design and layout of your
website. 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? Superb work!
Very good info. Lucky me I came across your website by chance (stumbleupon).
I’ve book-marked it for later!
I simply couldn’t go away your site before suggesting that
I actually loved the usual info an individual supply
on your guests? Is going to be again regularly to investigate cross-check new posts
Hello, for all time i used to check blog posts here early in the morning,
as i like to learn more and more.
My partner and I stumbled over here by a different web address and thought I may as well check things out. I like what I see so i am just following you. Look forward to exploring your web page repeatedly.
Remarkable things here. I am very satisfied to peer your
post. Thanks so much and I am having a look forward to
contact you. Will you kindly drop me a mail?
Hello to every , for the reason that I am really eager of reading this webpage’s post to
be updated on a regular basis. It contains pleasant data.
Thanks for sharing your thoughts. I really appreciate your
efforts and I am waiting for your next write ups thanks once again.
My developer is trying to convince 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 several websites for about a year and am
concerned 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 kind of help would be greatly appreciated!
Hola! I’ve been following your blog for some time now and
finally got the courage to go ahead and give you a shout out
from Porter Tx! Just wanted to mention keep up the
great job!
Unquestionably believe that which you stated. Your favorite justification seemed to be on the web the simplest thing to
be aware of. I say to you, I definitely get annoyed while
people consider worries that they plainly do not know about.
You managed to hit the nail upon the top as
well as defined out the whole thing without having side effect ,
people can take a signal. Will probably be back to get more.
Thanks
Hi there! Would you mind if I share your blog with my zynga group?
There’s a lot of folks that I think would really appreciate your content.
Please let me know. Cheers
Hello, I think your web site might be having web browser compatibility
problems. When I take a look at your website in Safari, it looks
fine but when opening in Internet Explorer, it has some overlapping issues.
I just wanted to provide you with a quick heads up! Besides that, wonderful site!
Howdy just wanted to give you a quick heads up. The words in your article seem
to be running off the screen in Opera. I’m not
sure if this is a format issue or something
to do with internet browser compatibility but I figured I’d post to let you know.
The design and style look great though! Hope you get the problem solved soon. Many thanks
Hi, yup this post is actually pleasant and I have learned lot of things from it regarding blogging.
thanks.
Wow, that’s what I was searching for, what a material!
present here at this web site, thanks admin of this web site.
Thanks for every other informative blog. The place else may I am getting that type of info written in such an ideal way?
I’ve a project that I am just now operating on, and I’ve
been on the look out for such information.
Perfectly indited articles, regards for information .