奇怪的二分+LCP
orz rky 考场上直接后缀平衡树秒掉
orz lyz 随手后缀数组秒掉
orz 两位2h AK SDOI2016 Day2的神犇
高二大爷们和wyx全AK了简直太可怕
因为我不敢写后缀数组（因为只写过2次），所以考场上GG咯
回来补一个二分LCP的做法
首先我们考虑两个后缀A,B对答案的贡献(已经按字典序排序)
贡献是$|A|+|B|-LCP(A,B)$
那么我们用一个set动态维护就可以了
每次插入一个字符一定会多一个后缀
然后我们在set里面找一找前驱后继算一下就好了
下面是rky的神·题解
-------------------------------------------------
第一题因为要求每个字符添加后的答案，所以我们考虑每个字符添加后的贡献。
假设添加到第$i$个字符，如果不考虑重复，对答案的贡献就是$i$，
如果$S[j...i]$与前面某个子串重复且$j$为最小值，那么对答案的贡献就是$j-1$，
现在的问题就是求出$j$。
因为$S[j...i]$为$i$的后缀，所以我们可以把字符串翻转一下，
利用后缀数组可以很方便的求最长公共前缀，
但如果直接枚举j则还是超时的，
不过我们可以利用LCP一个巧妙的性质：
$LCP(i,j)>=LCP(i,k)(|rank[i]-rank[j]|<=|rank[i]-rank[k]|)$，
所以我们可以建一棵平衡树(以rank为关键字)，寻找j的时候就找一下j的前驱和后继，
取LCP最大值更新答案就可以了。
-------------------------------------------------
orz 你萌都会后缀+平衡树。。。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
using namespace std;
typedef long long LL;
const int N=100005;
const LL P=1e9+7;
int n,a[N];
LL Pow[N],Hash[N],ans;
LL GetHash(int l,int r){return (Hash[l]-Hash[r+1])*Pow[n-l];}
int LCP(int a,int b){
if(a>b)a^=b^=a^=b;
int l=0,r=n-b+2,ans=0;
while(l+1<r){
int mid=l+r>>1;
if(GetHash(a,a+mid-1)!=GetHash(b,b+mid-1)){r=mid;}
else {l=mid;ans=mid;}
}
return ans;
}
struct Cmp{
bool operator()(int A,int B){
int Lcp=LCP(A,B);
if(B+Lcp>n)return 0;
if(A+Lcp>n)return 1;
return a[A+Lcp]<a[B+Lcp];
}
};
set<int,Cmp> St;
void Solve(){
for(int i=n;i;i--){
set<int,Cmp>::iterator It,Pre,Nxt;
Hash[i]=Hash[i+1]+a[i]*Pow[i];
It=St.insert(i).first;
Pre=It;Pre--;Nxt=It;Nxt++;
ans+=n-i+1;
if(It!=St.begin())ans-=LCP(*Pre,*It);
if(Nxt!=St.end())ans-=LCP(*It,*Nxt);
if(It!=St.begin() && Nxt!=St.end())ans+=LCP(*Pre,*Nxt);
printf("%lld\n",ans);
}
}
template<typename T> void Read(T &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}
int main(){
freopen("4516.in","r",stdin);
freopen("4516.out","w",stdout);
Read(n);
for(int i=n;i;i--)Read(a[i]);
Pow[0]=1ll;
for(int i=1;i<=n;i++)Pow[i]=Pow[i-1]*P;
Solve();
return 0;
}
评论 (0)
