QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#263791 | #3293. 优秀的拆分 | linweitong | 100 ✓ | 757ms | 5464kb | C++14 | 4.2kb | 2023-11-25 07:31:34 | 2023-11-25 07:31:36 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=30005;
char str[N];
int n;
int rk[N*2],h[N],sa[N],rnk[N*2],now;
bool cmp(int x,int y){return rk[x]==rk[y]?(rk[x+now]<rk[y+now]):(rk[x]<rk[y]);}
void Sa(){
for (int i=1;i<=n;++i)rk[i]=str[i],sa[i]=i;
for (int j=1;j<n;j<<=1){
now=j;sort(sa+1,sa+n+1,cmp);
for (int i=1;i<=n;++i)rnk[i]=rk[i];
int tot=0;
for (int i=1;i<=n;++i){
if (rnk[sa[i]]!=rnk[sa[i-1]]||rnk[sa[i]+now]!=rnk[sa[i-1]+now]||i==1)++tot;
rk[sa[i]]=tot;
}
}
for (int i=1,p=0;i<=n;++i){
if (p)--p;
while (str[i+p]==str[sa[rk[i]-1]+p]&&i+p<=n&&sa[rk[i]-1]+p<=n)++p;
h[rk[i]]=p;
}
}
int A[N],B[N],f[N],g[N];
struct BIT{
int tr[N],top,st[N*3][2];
void add(int x,int v,bool ck){
if (!ck)st[++top][0]=x,st[top][1]=v;
for (int i=x;i<=n;i+=(i&(-i)))tr[i]+=v;
}
int qry(int x){
int s=0;
for (int i=x;i;i-=(i&(-i)))s+=tr[i];
return s;
}
int query(int x,int y){return x>y?0:(qry(y)-qry(x-1));}
void del(){
while (top)add(st[top][0],-st[top][1],1),--top;
}
}T;
void solve1(int l,int r){
if (l==r)return;
int mid=(l+r)>>1;
A[mid]=n+1;
for (int i=mid-1;i>=l;--i)A[i]=min(A[i+1],h[i+1]);
B[mid+1]=h[mid+1];
for (int i=mid+2;i<=r;++i)B[i]=min(B[i-1],h[i]);
int j=mid;
for (int i=mid;i>=l;--i){
while (A[i]<B[j+1]&&j+1<=r){
++j;
T.add(sa[j],1,0);
}
if (sa[i]^n)f[sa[i]]+=T.query(sa[i]+1,min(n,sa[i]+A[i]));
}
T.del();
j=r+1;
for (int i=l;i<=mid;++i){
while (A[i]>=B[j-1]&&j-1>=mid+1){
--j;
if (sa[j]==1)continue;
int u=sa[j]-B[j],v=sa[j]-1;
if (u<=v){
u=max(u,1);
T.add(u,1,0),T.add(v+1,-1,0);
}
}
f[sa[i]]+=T.qry(sa[i]);
}
T.del();
solve1(l,mid),solve1(mid+1,r);
}
void solve2(int l,int r){
if (l==r)return;
int mid=(l+r)>>1;
A[mid]=n+1;
for (int i=mid-1;i>=l;--i)A[i]=min(A[i+1],h[i+1]);
B[mid+1]=h[mid+1];
for (int i=mid+2;i<=r;++i)B[i]=min(B[i-1],h[i]);
int j=l-1;
for (int i=r;i>=mid+1;--i){
while (j+1<=mid&&A[j+1]<B[i]){
++j;
if (sa[j]==1)continue;
int u=sa[j]-A[j],v=sa[j]-1;
if (u<=v){
u=max(u,1);
T.add(u,1,0),T.add(v+1,-1,0);
}
}
f[sa[i]]+=T.qry(sa[i]);
}
T.del();
j=mid+1;
for (int i=mid+1;i<=r;++i){
while (j-1>=l&&A[j-1]>=B[i]){
--j;
T.add(sa[j],1,0);
}
if (sa[i]^n)f[sa[i]]+=T.query(sa[i]+1,min(sa[i]+B[i],n));
}
T.del();
solve2(l,mid),solve2(mid+1,r);
}
void solve3(int l,int r){
if (l==r)return;
int mid=(l+r)>>1;
A[mid]=n+1;
for (int i=mid-1;i>=l;--i)A[i]=min(A[i+1],h[i+1]);
B[mid+1]=h[mid+1];
for (int i=mid+2;i<=r;++i)B[i]=min(B[i-1],h[i]);
int j=mid;
for (int i=mid;i>=l;--i){
while (A[i]<B[j+1]&&j+1<=r){
++j;
T.add(sa[j],1,0);
}
if (sa[i]^n)g[sa[i]]+=T.query(sa[i]+1,min(n,sa[i]+A[i]));
}
T.del();
j=r+1;
for (int i=l;i<=mid;++i){
while (A[i]>=B[j-1]&&j-1>=mid+1){
--j;
if (sa[j]==1)continue;
int u=sa[j]-B[j],v=sa[j]-1;
if (u<=v){
u=max(u,1);
T.add(u,1,0),T.add(v+1,-1,0);
}
}
g[sa[i]]+=T.qry(sa[i]);
}
T.del();
solve3(l,mid),solve3(mid+1,r);
}
void solve4(int l,int r){
if (l==r)return;
int mid=(l+r)>>1;
A[mid]=n+1;
for (int i=mid-1;i>=l;--i)A[i]=min(A[i+1],h[i+1]);
B[mid+1]=h[mid+1];
for (int i=mid+2;i<=r;++i)B[i]=min(B[i-1],h[i]);
int j=l-1;
for (int i=r;i>=mid+1;--i){
while (j+1<=mid&&A[j+1]<B[i]){
++j;
if (sa[j]==1)continue;
int u=sa[j]-A[j],v=sa[j]-1;
if (u<=v){
u=max(u,1);
T.add(u,1,0),T.add(v+1,-1,0);
}
}
g[sa[i]]+=T.qry(sa[i]);
}
T.del();
j=mid+1;
for (int i=mid+1;i<=r;++i){
while (j-1>=l&&A[j-1]>=B[i]){
--j;
T.add(sa[j],1,0);
}
if (sa[i]^n)g[sa[i]]+=T.query(sa[i]+1,min(sa[i]+B[i],n));
}
T.del();
solve4(l,mid),solve4(mid+1,r);
}
void solve(){
scanf("%s",str+1);
n=strlen(str+1);
Sa();
solve1(1,n);
solve2(1,n);
for (int i=1;i*2<=n;++i)swap(str[i],str[n-i+1]);
for (int i=0;i<=2*n;++i)rk[i]=rnk[i]=0;
Sa();
solve3(1,n);
solve4(1,n);
ll ans=0;
for (int i=1;i*2<=n;++i)swap(g[i],g[n-i+1]);
for (int i=1;i<=n;++i)ans+=1ll*f[i]*g[i-1];
for (int i=0;i<=n;++i)f[i]=g[i]=h[i]=0;
for (int i=0;i<=2*n;++i)rk[i]=rnk[i]=0;
printf("%lld\n",ans);
}
int main(){
int T;
scanf("%d",&T);
while (T--)solve();
}
详细
Test #1:
score: 5
Accepted
time: 3ms
memory: 4032kb
input:
10 wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk...
output:
462056 140600 875978 575960 811035 299536 173880 414090 227128 924490
result:
ok 10 numbers
Test #2:
score: 5
Accepted
time: 3ms
memory: 3956kb
input:
10 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
369564 513590 285760 308945 408312 190568 180441 328350 437635 1091574
result:
ok 10 numbers
Test #3:
score: 5
Accepted
time: 26ms
memory: 4068kb
input:
10 kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk...
output:
92601930 126763350 233408728 111659395 147774025 41791750 62056280 198982282 172593608 298613460
result:
ok 10 numbers
Test #4:
score: 5
Accepted
time: 24ms
memory: 4044kb
input:
10 nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn...
output:
241383298 63369600 53220335 75846485 53073182 47276061 287600152 128609208 205431400 71461299
result:
ok 10 numbers
Test #5:
score: 5
Accepted
time: 0ms
memory: 3884kb
input:
10 nnnnnnnnnn hzhzhzhzhz zezezezeze ndndndndnd zvzvzvzvzv bbbbbbbbbb sgsgsgsgsg fgfgfgfgfg hxhxhxhxhx fafafafafa
output:
30 3 3 3 3 30 3 3 3 3
result:
ok 10 numbers
Test #6:
score: 5
Accepted
time: 0ms
memory: 3956kb
input:
10 xxxxxxxxxx wtwtwtwtwt sososososo xgxgxgxgxg lblblblblb rororororo qfqfqfqfqf qjqjqjqjqj upupupupup nynynynyny
output:
30 3 3 3 3 3 3 3 3 3
result:
ok 10 numbers
Test #7:
score: 5
Accepted
time: 0ms
memory: 4016kb
input:
10 jjjjjjjjjjjjjjjjjjjj tgtgtgtgtg mcomcomcomco wthwthwthwth aaitaaitaaitaait pvaompvaompvaompvaom ahahahahah jwxmjwxmjwxmjwxm pdfpdfpdfpdf oiyfoiyfoiyfoiyf
output:
285 3 1 1 5 1 3 1 1 1
result:
ok 10 numbers
Test #8:
score: 5
Accepted
time: 0ms
memory: 3960kb
input:
10 iiiiiiiiiiiiiiiii scscscscscscsc bsobsobsobsobso rppyrppyrppyrppy xhnxhnxhnxhn jfbjfbjfbjfb tqtqtqtqtq cdocdocdocdocdo imgimgimgimg zxzxzxzxzx
output:
168 13 4 5 1 1 3 4 1 3
result:
ok 10 numbers
Test #9:
score: 5
Accepted
time: 1ms
memory: 3964kb
input:
10 sssssssssssssssssssss wawawawawawawawa xlexlexlexlexlexlexle cwqfcwqfcwqfcwqfcwqfcwqfcwqf dappidappidappidappidappi biwtbbiwtbbiwtbbiwtb ipdbipdbipdbipdb oyqjoyqjoyqjoyqj miqozmiqozmiqozmiqoz ofqgofqgofqgofqg
output:
330 22 18 23 14 3 1 1 1 1
result:
ok 10 numbers
Test #10:
score: 5
Accepted
time: 1ms
memory: 3832kb
input:
10 zzzzzzzzzzzzzzzzzzzzzzzzzzz icicicicicicicicicicic saasaasaasaasaasaasaa znunznunznunznunznun ttfhhttfhhttfhhttfhhttfhh fqxqblfqxqblfqxqblfqxqblfqxqbl xxpruxxpruxxpruxxpru mpheqsmpheqsmpheqsmpheqs ptvbemqptvbemqptvbemqptvbemq nxykqknxykqknxykqknxykqk
output:
728 70 36 5 26 7 5 1 1 1
result:
ok 10 numbers
Test #11:
score: 5
Accepted
time: 1ms
memory: 3972kb
input:
10 jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj ibibibibibibibibibibibibibibibibibibibibibibibib xinxinxinxinxinxinxinxinxinxinxin ivlwivlwivlwivlwivlwivlw cxrvucxrvucxrvucxrvucxrvucxrvucxrvucxrvucxrvu jzqfmgjzqfmgjzqfmgjzqfmgjzqfmg nqctlysnqctlysnqctlysnqctlysnqctlysnqctlysnqctlys kuizuntnkuizuntnkuizuntnkuizu...
output:
1240 946 100 11 76 7 38 9 18 1
result:
ok 10 numbers
Test #12:
score: 5
Accepted
time: 1ms
memory: 4016kb
input:
10 vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv dvdvdvdvdvdvdvdvdvdvdvdvdv jhyjhyjhyjhyjhyjhyjhyjhyjhy dkbjdkbjdkbjdkbjdkbjdkbjdkbjdkbj ezlbtezlbtezlbtezlbtezlbtezlbtezlbtezlbt efwduoefwduoefwduoefwduoefwduoefwduoefwduo eqgdlgxeqgdlgxeqgdlgxeqgdlgxeqgdlgxeqgdlgx mwuoqleamwuoqleamwuoqleamwuoqlea gwcbhodfpgwcb...
output:
1632 125 48 38 46 33 17 1 1 5
result:
ok 10 numbers
Test #13:
score: 5
Accepted
time: 1ms
memory: 3968kb
input:
10 vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv xwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxwxw rslrslrslrslrslrslrslrslrslrslrslrslrslrslrslrslrslrslrslrslrslrslrslrsl iimeiimeiimeiimeiimeiimeiimeiimeiimeiimeiimeiime...
output:
25585 6391 1386 1014 876 567 62 118 33 86
result:
ok 10 numbers
Test #14:
score: 5
Accepted
time: 0ms
memory: 3964kb
input:
10 rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr ozozozozozozozozozozozozozozozozozozozozozozozozozozozozozozozoz ysvysvysvysvysvysvysvysvysvysvysvysvysvysvysvysvysvysv ipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbdipbd x...
output:
19019 2360 540 1826 110 7 511 118 132 53
result:
ok 10 numbers
Test #15:
score: 5
Accepted
time: 2ms
memory: 3956kb
input:
10 ssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss vzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvzvz yzkyzkyzkyzkyzk...
output:
155155 18445 7600 13475 3328 72 114 37 17 6
result:
ok 10 numbers
Test #16:
score: 5
Accepted
time: 1ms
memory: 3916kb
input:
10 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii bxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbxbx...
output:
281295 48503 26100 13475 20516 80 72 59 21 26
result:
ok 10 numbers
Test #17:
score: 5
Accepted
time: 3ms
memory: 3988kb
input:
10 iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii...
output:
1391040 981179 345415 50677 52576 227 28 413 144 50
result:
ok 10 numbers
Test #18:
score: 5
Accepted
time: 14ms
memory: 3876kb
input:
10 fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff...
output:
38263590 33623065 4070400 510708 624588 2102 1074 299 408 1538
result:
ok 10 numbers
Test #19:
score: 5
Accepted
time: 31ms
memory: 4052kb
input:
10 qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq...
output:
245030555 46877978 4884100 14318590 12858978 5063 5381 7598 4729 5228
result:
ok 10 numbers
Test #20:
score: 5
Accepted
time: 757ms
memory: 5464kb
input:
10 yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyy...
output:
563349754956 161455324997 76621205738 70150901846 40842068960 6056659 2820346 3357795 2628223 10884
result:
ok 10 numbers
Extra Test:
score: 0
Extra Test Passed