https:\/\/gist.github.com\/lychees\/7079186<\/a><\/p>\n\r\nconst int N = int(1e5)+9, M = 26+1, LV = 20;\r\n \r\nLL a[N]; char s[N]; int n;\r\nint C[N], key[N], t1[N], t2[N];\r\n \r\nstruct SA{\r\n \r\n int a[3*N], sa[3*N], rk[N], h[N];\r\n \r\n inline void rs(int*x,int*y,int*sa,int n,int m){\r\n REP(i, n)key[i]=i[y][x];\r\n memset(C, 0,sizeof(C[0])*m);\r\n REP(i, n) ++C[key[i]];\r\n FOR(i, 1, m) C[i] += C[i-1];\r\n DWN(i, n, 0) sa[--C[key[i]]] = y[i];\r\n }\r\n \r\n void da(int*a,int*sa,int n,int m){\r\n int *x = t1, *y = t2;\r\n memset(C,0,sizeof(C[0])*m);\r\n REP(i, n)++C[x[i]=a[i]];\r\n FOR(i, 1, m)C[i]+=C[i-1];\r\n DWN(i, n, 0)sa[--C[x[i]]]=i;\r\n for(int l=1,p=1;p<n;l<<=1,m=p){\r\n p=0; FOR(i, n-l, n) y[p++]=i;\r\n REP(i, n) if (sa[i]>=l) y[p++]=sa[i]-l;\r\n rs(x,y,sa,n,m),swap(x,y),x[sa[0]]=p=0;FOR(i, 1, n)\r\n x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+l]==y[sa[i-1]+l])?p:++p;\r\n ++p;\r\n }\r\n }\r\n \r\n#define F(x) ((x)\/3+((x)%3==1?0:tb))\r\n#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)\r\nint c0(int*r,int a,int b)\r\n{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}\r\nint c12(int k,int*r,int a,int b)\r\n{if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);\r\n else return r[a]<r[b]||r[a]==r[b]&&key[a+1]<key[b+1];}\r\n \r\nvoid dc3(int*a,int*sa,int n,int m){\r\n int i, j, *an=a+n, *san=sa+n, ta=0, tb=(n+1)\/3, tbc=0, p;\r\n a[n] = a[n+1] = 0; REP(i, n) if (i%3) t1[tbc++]=i;\r\n \r\n rs(a+2,t1,t2,tbc,m),rs(a+1,t2,t1,tbc,m),rs(a,t1,t2,tbc,m);\r\n p=0,an[F(t2[0])]=0;FOR(i, 1, tbc)\r\n an[F(t2[i])]=c0(a,t2[i-1],t2[i])?p:++p;\r\n \r\n if (++p < tbc) dc3(an,san,tbc,p);\r\n else REP(i, tbc) san[an[i]] = i;\r\n \r\n REP(i, tbc) if(san[i] < tb) t2[ta++] = san[i] * 3;\r\n if (n%3==1) t2[ta++] = n-1; rs(a,t2,t1,ta,m);\r\n REP(i, tbc) key[t2[i]=G(san[i])] = i;\r\n \r\n for(i=0,j=0,p=0; i<ta && j<tbc; p++)\r\n sa[p]=c12(t2[j]%3,a,t1[i],t2[j]) ? t1[i++] : t2[j++];\r\n for(;i<ta;p++) sa[p]=t1[i++]; for(;j<tbc;p++) sa[p]=t2[j++];\r\n}\r\n \r\nvoid get_h(){\r\n REP_1(i, n) rk[sa[i]] = i;\r\n int k=0;for(int i=0;i<n;h[rk[i++]]=k){\r\n if (k)--k;for(int j=sa[rk[i]-1];a[i+k]==a[j+k];++k);\r\n }\r\n}\r\n \r\nint ST[LV][N];\r\n \r\n#define cmp(a, b) (h[a]<h[b]?a:b)\r\n \r\ninline int lcp(int l, int r){\r\n int lv = lg2(r - l); ++l, ++r;\r\n return min(h[ST[lv][l]], h[ST[lv][r-_1(lv)]]);\r\n}\r\n \r\ninline int lcpp(int l, int r){\r\n if (l == r) return n-l;\r\n l = rk[l], r = rk[r]; if (l > r) swap(l, r);\r\n return lcp(l, r);\r\n}\r\n \r\nvoid get_lcp(){\r\n REP_1(i, n) ST[0][i] = i;\r\n for (int lv = 1; _1(lv) <= n; ++lv){\r\n for (int i = 1; i + _1(lv) <= n + 1; ++i)\r\n ST[lv][i] = cmp(ST[lv-1][i], ST[lv-1][i+_1(lv-1)]);\r\n }\r\n}\r\n \r\nvoid bd(){\r\n dc3(a,sa,n+1,M),get_h(),get_lcp();\r\n}\r\n} A, B;\r\n \r\nPII get(LL k){\r\n int r = lower_bound(a, a+n, k) - a; k -= a[r-1];\r\n return MP(A.sa[r]+1, A.h[r]+k);\r\n}\r\n \r\nLL f(LL x, LL y){\r\n if (x>a[n] || y>a[n]) return -1;\r\n PII a = get(x), b = get(y); int t = min(a.se, b.se);\r\n return sqr(LL(min(t,A.lcpp(a.fi-1, b.fi-1)))) + sqr(LL(min(t,B.lcpp(n-(a.fi+a.se-1), n-(b.fi+b.se-1)))));\r\n}\r\n \r\n \r\nint main(){\r\n \r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n \r\n int m; RD(n, m); strlen(RS(s)); REP(i, n) B.a[n-i-1]=A.a[i]=s[i]-='a'-1;\r\n A.bd(); B.bd(); REP_1(i, n) a[i]=a[i-1]+n-A.sa[i]-A.h[i];\r\n DO(m) OT(f(RD(), RD()));\r\n}\r\n<\/pre>\nExternal link:<\/h3>\n
http:\/\/www.lydsy.com:808\/JudgeOnline\/problem.php?id=3230<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"Brief description: \u8bbe\u4e24\u4e2a\u5b57\u7b26\u4e32\u7684\u6700\u957f\u516c\u5171\u524d\u7f00\u548c\u540e\u7f00\u7684\u957f\u5ea6\u5206\u522b\u4e3a $$a$$, $$b$$\u3002 \u5219\u5b83\u4eec\u76f8\u4f3c\u7a0b\u5ea6\uff0c\u5b9a\u4e49\u4e3a $$a^2 + b^2$$\u3002 \u7ed9\u5b9a\u4e00\u4e2a\u5b57\u7b26\u4e32\uff0c\u6bcf\u6b21\u8be2\u95ee\u5176\u5b57\u5178\u5e8f\u7b2c k1-th \u5927\u548c\u7b2c k2-th \u5927\u7684\u4e24\u4e2a\u5b50\u4e32\u95f4\u7684\u76f8\u4f3c\u7a0b\u5ea6\u3002<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[22],"tags":[123],"class_list":["post-841","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-123"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-dz","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/841","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=841"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/841\/revisions"}],"predecessor-version":[{"id":842,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/841\/revisions\/842"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=841"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=841"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=841"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}