装饰工程东莞网站建设,生产erp管理系统app,wordpress禁止下载图片,大埔网站建设题面见http://uoj.ac/problem/131 一道后缀数组题 先求出height#xff0c;然后从大到小枚举每个height。 然后对于每个height值#xff0c;两端的集合中任意一对后缀的LCP都是这个height。 我们统计答案之后合并两端的集合#xff0c;用并查集维护即可。 1 #includecst…题面见http://uoj.ac/problem/131 一道后缀数组题 先求出height然后从大到小枚举每个height。 然后对于每个height值两端的集合中任意一对后缀的LCP都是这个height。 我们统计答案之后合并两端的集合用并查集维护即可。 1 #includecstdio2 #includeiostream3 #includecmath4 #includecstring5 #includealgorithm6 #define maxn 3000057 #define inf 1LL628 using namespace std;9 typedef long long int64;
10 char ch,s[maxn];
11 int n,val[maxn];
12 int64 ans[2][maxn];
13 int fa[maxn],siz[maxn],list[maxn],max_val[maxn],min_val[maxn];
14 int SA[maxn],rank[maxn],height[maxn],sum[maxn],t1[maxn],t2[maxn];
15 bool cmp(int x,int y){
16 if (height[x]!height[y]) return height[x]height[y];
17 return xy;
18 }
19 bool ok;
20 void read(int x){
21 for (ok0,chgetchar();!isdigit(ch);chgetchar()) if (ch-) ok1;
22 for (x0;isdigit(ch);xx*10ch-0,chgetchar());
23 if (ok) x-x;
24 }
25 void get_SA(){
26 int *xt1,*yt2,m255,tot0;
27 for (int i1;in;i) sum[x[i]s[i]];
28 for (int i1;im;i) sum[i]sum[i-1];
29 for (int in;i1;i--) SA[sum[x[i]]--]i;
30 for (int len1;totn;len1,mtot){
31 tot0;
32 for (int in-len1;in;i) y[tot]i;
33 for (int i1;in;i) if (SA[i]len) y[tot]SA[i]-len;
34 for (int i1;im;i) sum[i]0;
35 for (int i1;in;i) sum[x[y[i]]];
36 for (int i1;im;i) sum[i]sum[i-1];
37 for (int in;i1;i--) SA[sum[x[y[i]]]--]y[i];
38 swap(x,y),x[SA[1]]tot1;
39 for (int i2;in;i){
40 if (y[SA[i]]!y[SA[i-1]]||y[SA[i]len]!y[SA[i-1]len]) tot;
41 x[SA[i]]tot;
42 }
43 }
44 for (int i1;in;i) rank[i]x[i];
45 }
46 void get_height(){
47 for (int i1,j0;in;i){
48 if (rank[i]1) continue;
49 while (s[ij]s[SA[rank[i]-1]j]) j;
50 height[rank[i]]j;
51 if (j0) j--;
52 }
53 }
54 int find(int x){return fa[x]x?x:fa[x]find(fa[x]);}
55 void merge(int x,int y){
56 siz[y]siz[x];
57 max_val[y]max(max_val[y],max_val[x]);
58 min_val[y]min(min_val[y],min_val[x]);
59 fa[x]y;
60 }
61 int main(){
62 read(n);
63 scanf(%s,s1);
64 get_SA(),get_height();
65 for (int i1;in;i) read(val[i]);
66 for (int i1;in;i) max_val[i]val[SA[i]];
67 for (int i1;in;i) min_val[i]val[SA[i]];
68 for (int i1;in;i) fa[i]i;
69 for (int i1;in;i) siz[i]1;
70 for (int i1;in;i) list[i]i1;
71 for (int i1;in;i) ans[1][i]-inf;
72 sort(list1,listn,cmp);
73 for (int i1;in;i){
74 int xfind(list[i]-1),yfind(list[i]);
75 ans[0][height[list[i]]]1LL*siz[x]*siz[y];
76 ans[1][height[list[i]]]max(ans[1][height[list[i]]],1LL*max_val[x]*max_val[y]);
77 ans[1][height[list[i]]]max(ans[1][height[list[i]]],1LL*max_val[x]*min_val[y]);
78 ans[1][height[list[i]]]max(ans[1][height[list[i]]],1LL*min_val[x]*max_val[y]);
79 ans[1][height[list[i]]]max(ans[1][height[list[i]]],1LL*min_val[x]*min_val[y]);
80 merge(x,y);
81 }
82 for (int in-2;i0;i--) ans[0][i]ans[0][i1],ans[1][i]max(ans[1][i],ans[1][i1]);
83 for (int i0;in;i) printf(%lld %lld\n,ans[0][i],ans[0][i]?ans[1][i]:0);
84 return 0;
85 } 转载于:https://www.cnblogs.com/chenyushuo/p/4733941.html
