转载请注明出处:http://www.cnblogs.com/TSHugh/p/8779709.html
YJQ的题解把思路介绍得很明白,只不过有些细节说得还是太笼统了(不过正经的题解就应该这个样子吧).
我的思路和YJQ有一些不同.
首先:
然后:
(以上思路中的公式可能需要一定的微调,具体公式请读者在懂得思路后自行推断.)
以上就是我这道题思路的全部了.实现的话我用的是SAM和替罪羊启发式合并,竟然比线段树合并快……
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int A=;
const int N=;
const int M=;
const int Inf=0x3f3f3f3f;
const double alpha=0.75;
int n,m;
LL ans[M];
char s[N];
struct Q{
int to,next,id;
}q[M];
int mine[N<<],qt;
inline void add(int x,int y,int z){
q[++qt].to=y,q[qt].next=mine[x],mine[x]=qt,q[qt].id=z;
}
struct V{
int to,next;
}c[N<<];
int head[N<<],t;
inline void add(int x,int y){
c[++t].to=y,c[t].next=head[x],head[x]=t;
}
struct ScapeGoat_Tree{
ScapeGoat_Tree *ch[];
int size;
int key,max,min;
LL sum1,val1;
int sum2,val2;
inline void pushup(){
size=ch[]->size+ch[]->size+;
sum1=ch[]->sum1+ch[]->sum1+val1;
sum2=ch[]->sum2+ch[]->sum2+val2;
max=min=key;
max=std::max(max,ch[]->max);
max=std::max(max,ch[]->max);
min=std::min(min,ch[]->min);
min=std::min(min,ch[]->min);
}
inline bool isbad(){
return size*alpha+<ch[]->size||size*alpha+<ch[]->size;
}
inline void* operator new(size_t);
}*root[N<<],*null,*C,*mempool,*list[N];
inline void* ScapeGoat_Tree::operator new(size_t){
if(C==mempool){
C=new ScapeGoat_Tree[(<<)+];
mempool=C+(<<)+;
}
return C++;
}
int len;
inline void travel(ScapeGoat_Tree *p){
if(p==null)return;
travel(p->ch[]);
list[++len]=p;
travel(p->ch[]);
}
inline ScapeGoat_Tree *divide(int l,int r){
if(l>r)return null;
int mid=(l+r)>>;
list[mid]->ch[]=divide(l,mid-);
list[mid]->ch[]=divide(mid+,r);
list[mid]->pushup();
return list[mid];
}
inline void rebuild(ScapeGoat_Tree *&p){
if(p==null)return;
len=;
travel(p);
p=divide(,len);
}
inline ScapeGoat_Tree **insert(ScapeGoat_Tree *&p,int key,LL val1,int val2){
if(p==null){
p=new ScapeGoat_Tree;
p->ch[]=p->ch[]=null;
p->size=;
p->key=p->max=p->min=key;
p->sum1=p->val1=val1;
p->sum2=p->val2=val2;
return &null;
}
ScapeGoat_Tree **ret=insert(p->ch[key>p->key],key,val1,val2);
p->pushup();
if(p->isbad())ret=&p;
return ret;
}
inline void Insert(ScapeGoat_Tree *&p,int key,LL val1,int val2){
rebuild(*insert(p,key,val1,val2));
}
inline void update(ScapeGoat_Tree *p,int key){
if(p==null)return;
if(p->key<=key)update(p->ch[],key);
else{
if(p->ch[]->size==||p->ch[]->max<=key){
p->val1=(LL)p->key*(p->key-key);
p->val2=p->key-key;
}else update(p->ch[],key);
}
p->pushup();
}
inline int upper_bound(ScapeGoat_Tree *p,int key){
if(p==null)return ;
if(p->key<=key)return upper_bound(p->ch[],key);
else{
if(p->ch[]->size==||p->ch[]->max<=key)return p->key;
else return upper_bound(p->ch[],key);
}
}
inline int lower_bound(ScapeGoat_Tree *p,int key){
if(p==null)return ;
if(p->key>=key)return lower_bound(p->ch[],key);
else{
if(p->ch[]->size==||p->ch[]->min>=key)return p->key;
else return lower_bound(p->ch[],key);
}
}
inline void Insert(ScapeGoat_Tree *&p,int key){
update(p,key);
int pr=lower_bound(p,key);
Insert(p,key,pr?(LL)(key-pr)*key:,pr?key-pr:);
}
inline void query(ScapeGoat_Tree *p,int key,LL &sum,int &size){
if(p==null)return;
if(p->key<=key){
sum+=p->ch[]->sum1+p->val1;
size+=p->ch[]->sum2+p->val2;
query(p->ch[],key,sum,size);
}else
query(p->ch[],key,sum,size);
}
inline LL query(ScapeGoat_Tree *p,int len){
int r1=p->min,rn=p->max,ln=rn-len+;
LL sum1=,sum2=,ret=;
int size1=,size2=;
query(p,r1+len-,sum1,size1);
query(p,ln,sum2,size2);
if(size1<=size2)ret=;
else ret=sum1-sum2-(LL)(size1-size2)*ln;
if(ln<r1)ret+=(LL)(r1-len)*(r1-ln);
int prv=lower_bound(p,r1+len-),nxt=upper_bound(p,prv);
if(!nxt)ret+=(LL)((n-ln-)+(n-r1))*(r1-ln)>>;
else ret+=(LL)(r1-(prv-len+))*std::max(nxt-ln,);
return ret;
}
inline void dfs(ScapeGoat_Tree *p,ScapeGoat_Tree *&to){
if(p==null)return;
Insert(to,p->key);
dfs(p->ch[],to);
dfs(p->ch[],to);
}
int rt,sz,trans[N<<][],link[N<<],max[N<<],f[N<<][A],pos[N];
#define newnode(a) (max[++sz]=(a),sz)
inline int insert(int x,int last){
int w=last,nw=newnode(max[w]+),h,nh;
while(w&&!trans[w][x])trans[w][x]=nw,w=link[w];
if(!w)
link[nw]=rt;
else{
h=trans[w][x];
if(max[h]==max[w]+)
link[nw]=h;
else{
nh=newnode(max[w]+);
memcpy(trans[nh],trans[h],);
while(w&&trans[w][x]==h)trans[w][x]=nh,w=link[w];
link[nh]=link[h],link[nw]=link[h]=nh;
}
}
return nw;
}
inline void dfs(int x,int fa){
int i;
f[x][]=fa;
root[x]=null;
for(i=;i<A;++i)
f[x][i]=f[f[x][i-]][i-];
for(i=head[x];i;i=c[i].next)
dfs(c[i].to,x);
}
inline int ipos(int x,int len){
int i;
for(i=A-;i>=;--i)
if(max[f[x][i]]>=len)
x=f[x][i];
return x;
}
inline void dfs(int x){
int i,j,v;
for(i=head[x];i;i=c[i].next){
v=c[i].to;
dfs(v);
if(root[x]->size<root[v]->size)
std::swap(root[v],root[x]);
dfs(root[v],root[x]);
}
for(i=mine[x];i;i=q[i].next)
ans[q[i].id]=query(root[x],q[i].to);
}
int main(){
rt=newnode();
null=new ScapeGoat_Tree;
memset(null,,sizeof(*null));
null->ch[]=null->ch[]=null;
null->min=Inf,null->max=-Inf;
scanf("%d%d",&n,&m);
scanf("%s",s+);
int i,last=rt,l,r,x;
for(i=;i<=n;++i)
last=pos[i]=insert(s[i]-'',last);
for(i=;i<=sz;++i)
add(link[i],i);
dfs(,);
for(i=;i<=n;++i)
Insert(root[pos[i]],i);
for(i=;i<=m;++i){
scanf("%d%d",&l,&r);
x=ipos(pos[r],r-l+);
add(x,r-l+,i);
}
dfs();
LL sum=(LL)(n-)*(n-)>>;
for(i=;i<=m;++i)
printf("%lld\n",sum-ans[i]);
return ;
}
Kod