solve 2 (D J)
rank 138/744 18.55%
J题 做法：复制一份数组，拼接到原数组后面，然后求一段区间不同数字的个数。树状数组优化。
D题 做法：暴力枚举，然后用set去重。
I题 补题：
题意：给你一个长度为n的字符串，问这个字符串有多少种不同构的子串。
比如abc和acb,bac,bca,cab,cba同构。
思路：既然要求不同构的子串个数，我们不妨把6种同构字符串拼接在一起，建立SAM，对于每种串，都连接在root上，统计不同的子串个数。
那么，若子串里含有2种及以上的字符的时候，它有6种同构字符串，且一定都在SAM中存在，且被统计过。
所以，这种字符串每6个，价值为1。（其余5种都是同构的，所以不计数）
还有一种串，只由一种字符串组成，比如aaa,bbb,ccc,它们互相同构，这种只会有3种同构字符串。
怎么计算个数呢？很简单，只需要找到在原串中，最长连续单一子串的长度是多少便可，对于所有的单一串，这一个串包含它们所有。
所以答案就出来了。
贴代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+10;
char s[maxn];
int n;
int pa[maxn<<2],son[maxn<<2][27];
int deep[maxn<<2],cnt,root,last;
ll tot;
inline int newnode(int _deep){
deep[++cnt]=_deep;
return cnt;
}
inline void sam(int alp){
int np=newnode(deep[last]+1);
int u=last;
memset(son[np],0,sizeof son[np]);
while(u && !son[u][alp])son[u][alp]=np,u=pa[u];
if(!u)pa[np]=root;
else{
int v=son[u][alp];
if(deep[v]==deep[u]+1)pa[np]=v;
else{
int nv=newnode(deep[u]+1);
memcpy(son[nv],son[v],sizeof son[v]);
pa[nv]=pa[v],pa[v]=pa[np]=nv;
while(u&&son[u][alp]==v)son[u][alp]=nv,u=pa[u];
}
}
last=np;
tot+=deep[np]-deep[pa[np]];
}
inline void pre(){
cnt=0;
memset(son[1],0,sizeof son[1]);
root=last=newnode(0);
tot=0;
}
int main(){
while(scanf("%d",&n)!=EOF){
scanf("%s",s);
pre();
for(int i=0;i<n;i++){
if(s[i]=='a'){
s[i+n]='a';s[i+2*n]='b';s[i+3*n]='b';s[i+4*n]='c';s[i+5*n]='c';
}else if(s[i]=='b'){
s[i+n]='c';s[i+2*n]='a';s[i+3*n]='c';s[i+4*n]='a';s[i+5*n]='b';
}else{
s[i+n]='b';s[i+2*n]='c';s[i+3*n]='a';s[i+4*n]='b';s[i+5*n]='a';
}
}/**得到6种同构串,拼接**/
n+=5*n;
int ct=0;
for(int i=0;i<n;i++){
sam(s[i]-'a');ct++;
if(ct==n/6){
ct=0;
last=1;
}
}
ll tot2=1;
ll cnt2=1;
for(int i=1;i<n/6;i++){
if(s[i]==s[i-1]){
cnt2++;
tot2=max(tot2,cnt2);
}else{
cnt2=1;
}
}
//cout<<tot<<" "<<tot2<<endl;
printf("%lld
",(tot+3*tot2)/6);
}
return 0;
}