洛谷 P4248 [AHOI2013]差异 & P3181 [HAOI2016]找相同字符
链接
P4248 P3181
把这两道题放在一起是要讨论这样一个问题
对于一个已知 \(ht\) 的 \(S\),\(O(n)\) 求 \(\sum\limits_{1\le i
首先我们可以把上式写成 \(\sum\limits_{1\le i\le j}\sum\limits_{1\le j
int sta[N],pos[N],sum[N],now,ans;
inline int solve(){//\sum_{1\le i好了回到这两道题。
分析
P4248 [AHOI2013]差异
我们把题目的式子稍微化化，就是
\((n-1)\times\frac{n\times (n+1)}2-2\sum\limits_{1\le i
直接上。
P3181 [HAOI2016]找相同字符
我们发现发现这题要求的仍然是上面类似的东西，只是子串的来源被分到了两个字符串，这种情况，我们经常用一个特殊字符将两式连接起来一起处理。这样做了后我们发现会算多一部分，这是从某一个串选了两个子串的答案，所以我们只用把两个子串分别处理的结果减掉就好了。
代码
P4248 [AHOI2013]差异
#include
using namespace std;
#define int long long
#define in read()
inline int read(){
int p=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){p=p*10+c-'0';c=getchar();}
return p*f;
}
const int N=5e5+5;
int n,m,rk[N<<1],sa[N],ht[N];
struct llmmkk{
int fi,se,ref;
}st[N<<1],tmp[N<<1];
int cnt[N];
inline void jsort(){
for(int i=0;i<=n;i++)cnt[i]=0;
for(int i=1;i<=n;i++)cnt[st[i].se]++;
for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--)tmp[cnt[st[i].se]]=st[i],cnt[st[i].se]--;
for(int i=0;i<=n;i++)cnt[i]=0;
for(int i=1;i<=n;i++)cnt[tmp[i].fi]++;
for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--)st[cnt[tmp[i].fi]]=tmp[i],cnt[tmp[i].fi]--;
}
int ston[257];
inline void SA(string S){
n=S.length();
for(int i=0;i>S;SA(S);
ans=(n+1)*n/2*(n-1)-2*solve();
cout< P3181 [HAOI2016]找相同字符
#include
using namespace std;
#define int long long
#define in read()
inline int read(){
int p=0,f=1;
char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){p=p*10+c-'0';c=getchar();}
return p*f;
}
const int N=4e5+5;
int n,rk[N<<1],sa[N],ht[N];
struct llmmkk{
int fi,se,ref;
}st[N<<1],tmp[N<<1];
int cnt[N];
inline void jsort(){
for(int i=0;i<=n;i++)cnt[i]=0;
for(int i=1;i<=n;i++)cnt[st[i].se]++;
for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--)tmp[cnt[st[i].se]]=st[i],cnt[st[i].se]--;
for(int i=0;i<=n;i++)cnt[i]=0;
for(int i=1;i<=n;i++)cnt[tmp[i].fi]++;
for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
for(int i=n;i>0;i--)st[cnt[tmp[i].fi]]=tmp[i],cnt[tmp[i].fi]--;
}
int ston[257];
inline void SA(string S){
n=S.length();memset(ston,0,sizeof(ston));
for(int i=0;i>S>>T;
SA(S),tans-=solve();
SA(T),tans-=solve();
SA(S+'#'+T),tans+=solve();
cout<