迪哥的博客写得钛皓蜡，板子注释也很清晰。
所以这里只有题表辣。
差异：
首先拆柿子:
$$\sum_{i=1}^{n}{(n-2)*i+\frac{n*(n+1)}{2}}-\sum_{1\leq i< j\leq n}{2*lcp(i,j)}$$
$$n*(n-1)*(n+1)-\sum_{1\leq i< j\leq n}{2*lcp(i,j)}$$
后面的$lcp$可以用单调栈求出每个$height(i)$控制的区间，$O(n)$解决。
注意一个$height$对应区间长度的至少是$2$，并且$height(1)$无用。
Sandy的卡片：
把字符串加上分割符建$sa$，然后二分长度，$O(n*logn)$。
相似子串:
手玩发现子串的排名和子串所在的后缀有关。
把每个后缀串控制的排名范围求出，即可$lower_bound$出排名对应的子串。
正反建$sa$，$ST$表维护公共前缀即可。
品酒大会：
第一问和差异一样，第二问直接$mid$的两边$ST$表。
因为“$r$相似同时也是$r-1$相似的”，所以要后缀取$\max$，然而窝脑抽打的线段树区间修改。
注意数据结构的操作是套在$rk$上的，下标取值一定要写对。
字符串：
读错题了。。。
询问是“子串$s[a..b]$的所有子串”和“$s[c..d]$”的最长公共前缀。
两种解法：
1>大神做法：
二分答案，对$rk$维护主席树。当有$mid$时，后缀可取区间为$[a,b-mid+1]$。
那么在区间$[a,b-mid+1]$的主席树上查的前驱后继一定是在排名上最接近以$c$开头的后缀。
也是$lcp$最大的位置，判断即可。
2>常数巨大的做法：
也二分长度，根据$mid$再二分出排名上符合$lcp>=mid$的区间，
然后用主席树判断$[a,b-mid+1]$是否有在合法范围的排名。
理论上也是一个$log$。
喵星球上的点名：
数据比较水，暴扫可过。
看网上有十几种做法，字符串家族八仙过海。
这里采纳了一个很实用很清真的树状数组做法。
第一问：
数颜色，可用主席树。
树状数组的做法是先离线，求每个颜色的$pre$。
然后边扫边统计答案，到某个颜色时把$pre$上的贡献删掉，前缀做差得答案。
原理是只留下了一个区间同种颜色的最后一个。
第二问：
也是边扫边用树状数组。
扫到位置$i$，把询问区间左端点在$i$上的加入。
$i$与$pre[i]$前缀和相减得到左端点在这之间的个数。
接下来把区间右端点在$i$的左端点的位置贡献减去，保证了不会统计到夹在$i$到$pre[i]$的区间。
神仙树状数组做法。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<vector> 5 #define MAXN 490001 6 #define lowbit(x) (x&-x) 7 using namespace std; 8 inline int read(){ 9 int s=0,w=0;char ch=getchar(); 10 while(ch<'0'||ch>'9')w|=(ch=='-'),ch=getchar(); 11 while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar(); 12 return w?-s:s; 13 } 14 #define kd (read()) 15 int x[MAXN],y[MAXN],c[MAXN]; 16 int a[MAXN],sa[MAXN],rk[MAXN],h[MAXN]; 17 int n,m; 18 int f[19][MAXN]; 19 int LOG[MAXN]; 20 inline int Getmn(int l,int r){ 21 if(r<l)return 0x7fffffff; 22 int len=LOG[r-l+1]; 23 return min(f[len][l],f[len][r-(1<<len)+1]); 24 } 25 void init(){ 26 m=10002; 27 for(int i=1;i<=m;++i)c[i]=0; 28 for(int i=1;i<=n;++i)++c[x[i]=a[i]]; 29 for(int i=1;i<=m;++i)c[i]+=c[i-1]; 30 for(int i=1;i<=n;++i)sa[c[x[i]]--]=i; 31 for(int len=1;len<=n;len<<=1){ 32 int num=0; 33 for(int i=n-len+1;i<=n;++i)y[++num]=i; 34 for(int i=1;i<=n;++i)if(sa[i]>len)y[++num]=sa[i]-len; 35 for(int i=1;i<=m;++i)c[i]=0; 36 for(int i=1;i<=n;++i)++c[x[i]]; 37 for(int i=1;i<=m;++i)c[i]+=c[i-1]; 38 for(int i=n;i>=1;--i)sa[c[x[y[i]]]--]=y[i]; 39 for(int i=1;i<=n;++i)y[i]=x[i],x[i]=0; 40 x[sa[1]]=m=1; 41 for(int i=2;i<=n;++i)x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&y[sa[i]+len]==y[sa[i-1]+len])?m:++m; 42 if(m==n)break; 43 } 44 for(int i=1;i<=n;++i)rk[sa[i]]=i; 45 for(int i=1,k=0;i<=n;h[rk[i++]]=k,k=k?k-1:0) 46 while(a[i+k]==a[sa[rk[i]-1]+k])++k; 47 for(int i=1;i<=n;++i)f[0][i]=h[i]; 48 for(int j=1;j<=18;++j) 49 for(int i=1;i+(1<<j)-1<=n;++i) 50 f[j][i]=min(f[j-1][i],f[j-1][i+(1<<j-1)]); 51 return ; 52 } 53 int N,M; 54 int nw[MAXN],pre[MAXN]; 55 int belong[MAXN],id[MAXN],Len[MAXN]; 56 int an1[MAXN],an2[MAXN]; 57 int C[MAXN]; 58 inline void addC(int pos,int val){ 59 if(!pos)return ; 60 for(;pos<=n;pos+=lowbit(pos))C[pos]+=val; 61 return ; 62 } 63 inline int Getsm(int pos){ 64 int res=0; 65 for(;pos;pos-=lowbit(pos))res+=C[pos]; 66 return res; 67 } 68 struct node{ 69 int l,r,idx; 70 }; 71 vector<node >td[MAXN]; 72 vector<int >dd[MAXN]; 73 int lei[MAXN]; 74 int main(){ 75 //freopen("da.in","r",stdin); 76 //freopen("2.out","w",stdout); 77 78 N=kd,M=kd; 79 for(int i=1,llen,tmp;i<=N;++i){ 80 llen=kd; 81 while(llen--)tmp=kd+1,a[++n]=tmp,belong[n]=i; 82 a[++n]=10002; 83 llen=kd; 84 while(llen--)tmp=kd+1,a[++n]=tmp,belong[n]=i; 85 a[++n]=10002; 86 } 87 for(int i=1,llen,tmp;i<=M;++i){ 88 id[i]=n+1;Len[i]=llen=kd; 89 while(llen--)tmp=kd+1,a[++n]=tmp; 90 a[++n]=10002; 91 } 92 for(int i=2;i<=n;++i)LOG[i]=LOG[i>>1]+1; 93 init(); 94 for(int i=1;i<=M;++i){ 95 int l=1,r=rk[id[i]],posl=0,posr=0; 96 while(r-l>1){ 97 int mid=l+r>>1; 98 if(Getmn(mid+1,rk[id[i]])>=Len[i])r=mid; 99 else l=mid; 100 } 101 if(Getmn(l+1,rk[id[i]])>=Len[i])posl=l; 102 else posl=r; 103 l=rk[id[i]],r=n; 104 while(r-l>1){ 105 int mid=l+r>>1; 106 if(Getmn(rk[id[i]]+1,mid)>=Len[i])l=mid; 107 else r=mid; 108 } 109 if(Getmn(rk[id[i]]+1,r)>=Len[i])posr=r; 110 else posr=l; 111 td[posr].push_back((node){posl,posr,i}); 112 dd[posr].push_back(posl); 113 ++lei[posl]; 114 //cout<<posl<<" "<<posr<<endl; 115 } 116 for(int i=1;i<=n;++i) 117 if(belong[sa[i]]){ 118 pre[i]=nw[belong[sa[i]]]; 119 nw[belong[sa[i]]]=i; 120 } 121 for(int i=1;i<=n;++i){ 122 if(belong[sa[i]]){ 123 addC(pre[i],-1); 124 addC(i,1); 125 } 126 for(int k=0;k<td[i].size();++k){ 127 node tmp=td[i][k]; 128 an1[tmp.idx]=Getsm(tmp.r)-Getsm(tmp.l-1); 129 } 130 } 131 for(int i=1;i<=M;++i)printf("%d\n",an1[i]); 132 for(int i=0;i<=n;++i)C[i]=0; 133 for(int i=1;i<=n;++i){ 134 addC(i,lei[i]); 135 if(belong[sa[i]]) 136 an2[belong[sa[i]]]+=Getsm(i)-Getsm(pre[i]); 137 for(int k=0;k<dd[i].size();++k)addC(dd[i][k],-1); 138 } 139 for(int i=1;i<=N;++i)printf("%d ",an2[i]); 140 puts(""); 141 142 return 0; 143 }
外星联络：
发现$N$很小，枚举子串，单调指针随便扫。
SvT：
排完序，$unique$就变成"队长快跑"辣，然后线段树常数很大是卡过的。
仍然可以用$h$控制区间跨区间乘法原理的思想。
大神都不写线段树。
总结：
单调栈，二分很常见。
建完$sa$就变成数据结构题辣！
$hash$暴力能能刚好多题。。。