【NOI2016】优秀的拆分

Source and Judge

NOI2016
uoj219

Analysis

请先思考后再展开

本题的套路和bzoj2119(写了题解)是一样的,就是建立关键点
那么对于本题,如果能求出lf和rf表示某个位置作为端点的AA数量
对于AA,枚举长度,然后发现只要有向两边的lcp,就会对【左右端点都是区间】产生贡献,用差分求和得到lf和rf
时间复杂度为调和级数的log

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
typedef long long ll;
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
const int MAX_N=31000;
int bin[30],lg[MAX_N];
int n;
struct Sa
{
char ss[MAX_N];
int rk[MAX_N],sa[MAX_N],ct[MAX_N];
int wr[MAX_N*2],tmp[MAX_N];
void getsa()
{
memset(ct,0,sizeof ct);
for(int i=1;i<=n;i++) ct[rk[i]=ss[i]]++;
for(int i=1;i<MAX_N;i++) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--) sa[ct[rk[i]]--]=i;
int ln=1;
while(ln<n)
{
int tot=0;for(int i=1;i<=n;i++) if(sa[i]+ln>n) tmp[++tot]=sa[i];
for(int i=1;i<=n;i++) if(sa[i]-ln>=1) tmp[++tot]=sa[i]-ln;
memset(wr,0,sizeof wr);//debug
memset(ct,0,sizeof ct);
for(int i=1;i<=n;i++) ct[wr[tmp[i]]=rk[tmp[i]]]++;
for(int i=1;i<MAX_N;i++) ct[i]+=ct[i-1];
for(int i=n;i>=1;i--) sa[ct[wr[tmp[i]]]--]=tmp[i];
int cnt=1;rk[sa[1]]=1;
for(int i=2;i<=n;i++)
{
if(wr[sa[i-1]]!=wr[sa[i]] or wr[sa[i-1]+ln]!=wr[sa[i]+ln]) cnt++;
rk[sa[i]]=cnt;
}
ln*=2;
}
}
int hei[MAX_N];
void gethei()
{
int lst=0;
for(int i=1;i<=n;i++)
{
if(rk[i]==1) {hei[rk[i]]=0;continue;}
int j=sa[rk[i]-1];if(lst) lst--;
while(max(i,j)+lst<=n and ss[i+lst]==ss[j+lst]) lst++;
hei[rk[i]]=lst;
}
}
int mi[MAX_N][20];
void pre()
{
getsa();gethei();
for(int i=2;i<=n;i++) mi[i][0]=hei[i];
for(int i=1;i<20;i++) for(int j=2;j<=n-bin[i]+1;j++) mi[j][i]=min(mi[j][i-1],mi[j+bin[i-1]][i-1]);
}
int ask(int l,int r)
{
if(l<=0 or r<=0 or l>n or r>n) return 0;
if(l==r) return n-l+1;//debug
l=rk[l];r=rk[r];if(l>r) swap(l,r);
l++;int lgg=lg[r-l+1];
return min(mi[l][lgg],mi[r-bin[lgg]+1][lgg]);
}
}sa1,sa2;//1是原串
ll lf[MAX_N],rf[MAX_N];
char s[MAX_N];
void main()
{
bin[0]=1;for(int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;
lg[1]=0;for(int i=2;i<MAX_N;i++) lg[i]=lg[i>>1]+1;
int T;scanf("%d",&T);
while(T--)
{
memset(lf,0,sizeof lf);memset(rf,0,sizeof rf);
memset(s,0,sizeof s);
scanf("%s",s+1);n=strlen(s+1);
memcpy(sa1.ss,s,sizeof s);memcpy(sa2.ss,s,sizeof s);reverse(sa2.ss+1,sa2.ss+n+1);
sa2.pre();sa1.pre();
for(int ln=1;ln<=n/2;ln++)
for(int i=1;i+ln<=n;i+=ln)
{
int j=i+ln;
int minr=sa1.ask(i,j),minl=sa2.ask(n-i+2,n-j+2);
minl=min(minl,ln-1);minr=min(minr,ln);
if(ln<=minl+minr)
{
lf[i-minl]++;lf[i+minr-ln+1]--;//差分
rf[i-minl+ln*2-1]++;rf[i+minr+ln]--;
}
}
for(int i=1;i<=n;i++) lf[i]+=lf[i-1],rf[i]+=rf[i-1];
ll ans=0;for(int i=2;i<=n;i++) ans+=rf[i-1]*lf[i];
printf("%lld\n",ans);
}
}
};
int main()
{
srand(time(0));
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/f7b4.html
转载请注明出处,谢谢!