不错的题目

 

看似无法做，n<=5e4,8s，根号算法？

暴力一：

n^2，+SAM上找匹配点的right集合sz，失配了直接退出

暴力二：

O(m)

统计过lca=x的路径，

没法直接合并，就间接合并！

把所有形如(z,x)(x,y)的路径在原串所有出现位置打上标记

原串每个点维护结束路径(zi,x)和开始路径(x,yi)个数（实际上只有char=a[x]的位置才有值），然后乘起来就是贡献

打标记：

SAM匹配

麻烦事是：这个是往某个字符串前面加字符，但是要在字符串末尾位置打上标记

（和通常SAM末尾+字符，末尾位置打标记不同）

要用到后缀树、前缀树

(z,x)路径是前缀树

(x,y)路径是后缀树（反串前缀树）

把parent树建成前缀树，走一下。

 

建树：

（第一次建后缀树）

1.每个节点随便记录一个parent树子树里的后缀出现位置pos[x]

2.预处理parent树每个边第一个字符（最多26条边），

3.可能在边上，所以状态用(p,l)记录：下面是p点，在p点上方l处。

trans，根据l大小进行讨论

 

打标记：

trans打上tag

最后直接下放

 

结合

设阈值B

size<=B用暴力一，不递归了，O(B^2*n/B)

size>B用暴力二，分治树节点个数不超O(B)最多进行O(Bm)

B取sqrt(n)即可

 

容斥？

暴力二离线处理共线，显然会重复。分治到下一层的时候为上一层去重。

也是根据size选择去重方法

 

 

 

Code

// luogu-judger-enable-o2#include
      
       #define reg register int#define il inline#define fi first#define se second#define mk(a,b) make_pair(a,b)#define numb (ch^'0')using namespace std;typedef long long ll;template
       
        il void rd(T &x){    char ch;x=0;bool fl=false;    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);    for(x=numb;isdigit(ch=getchar());x=x*10+numb);    (fl==true)&&(x=-x);}template
        
         il void output(T x){
    if(x/10)output(x/10);putchar(x%10+'0');}template
         
          il void ot(T x){
    if(x<0) putchar('-'),x=-x;output(x);putchar(' ');}template
          
           il void prt(T a[],int st,int nd){
    for(reg i=st;i<=nd;++i) ot(a[i]);putchar('\n');}namespace Miracle{const int N=50005;int B;char s[N];int n,m;char a[N];struct node{    int nxt,to;}e[2*N];int hd[N],cnt;void add(int x,int y){    e[++cnt].nxt=hd[x];    e[cnt].to=y;    hd[x]=cnt;}ll ans;struct SAM{    int ch[2*N][26],cnt,len[2*N],fa[2*N];    int son[2*N][26],nd;    int tag[2*N],exi[2*N],ad[2*N],pos[2*N];    int sz[2*N];    char s[2*N];    SAM(){        cnt=nd=1;    }    void ins(int c,int l){        int p=nd;len[nd=++cnt]=l;        exi[cnt]=l;sz[cnt]=1;        pos[cnt]=l;                for(;p&&ch[p][c]==0;p=fa[p]) ch[p][c]=nd;        if(!p){            fa[nd]=1;return;        }        int q=ch[p][c];        if(len[q]==len[p]+1){            fa[nd]=q;return;        }        len[++cnt]=len[p]+1;        fa[cnt]=fa[q];fa[q]=fa[nd]=cnt;        for(reg i=0;i<26;++i) ch[cnt][i]=ch[q][i];        for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=cnt;    }    struct edge{        int nxt,to;    }e[2*N];    int hd[2*N],tot;    void add(int x,int y){        e[++tot].nxt=hd[x];        e[tot].to=y;hd[x]=tot;    }    void dfs(int x){
    //pushup sz!!!        for(reg i=hd[x];i;i=e[i].nxt){            int y=e[i].to;            dfs(y);            sz[x]+=sz[y];            if(!pos[x]) pos[x]=pos[y];        }    }    void pre(){//        cout<
           
            <
            
             &st,int c,int ok){ //and add tag if(st.fi==0) return; if(st.se==1){ //to son st.fi=son[st.fi][c]; st.se=len[st.fi]-len[fa[st.fi]]; }else{ int to=pos[st.fi]-len[st.fi]+st.se-1; if(s[to]-'a'==c){ st.se--; }else st.fi=0; } if(st.fi!=0&&ok){ ++tag[st.fi]; } return; } void pushdown(int x){ for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; tag[y]+=tag[x]; pushdown(y); } } void calc(){ pushdown(1);// cout<<" cnt "<
             
              <
              
               =1;--i) p=sam1.ch[p][a[sta[i]]-'a']; dfs3(sta[2],sta[1],p,-1); for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(vis[y]||y==fa) continue; dfs2(y,x); } sta[top--]=0;}void dfs4(int x,int fa){ dfs3(x,0,1,1); for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(y==fa||vis[y]) continue; dfs4(y,x); }}void fin(int x,int fa){ sz[x]=1; int mxsz=0; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to;if(vis[y]||y==fa) continue; fin(y,x); sz[x]+=sz[y]; mxsz=max(mxsz,sz[y]); } mxsz=max(mxsz,nowsz-sz[x]); if(mxsz<=nowsz/2){ rt=x; }}void dfs1(int x,int fa,pair
               
                p1,pair
                
                 p2){ sz[x]=1; sam1.trans(p1,a[x]-'a',1); sam2.trans(p2,a[x]-'a',1); for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(vis[y]||y==fa) continue; dfs1(y,x,p1,p2); sz[x]+=sz[y]; }}void divi(int x,int fa){// cout<<" divi "<
                 
                  <<" fa "<
                  
                   <<" ans "<
                   
                    <
                    
                     p1=mk(1,1),p2=mk(1,1); sam1.trans(p1,a[fa]-'a',0); sam2.trans(p2,a[fa]-'a',0); dfs1(x,0,p1,p2); //cout<<" a[fa] "<
                     
                      <
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      

 

总结

1.根号讨论暴力结合

2.点分治合并是难点，

要不然数据结构维护决策位置（树形Dp思路）

要不然都把上下路径都求出来放在一起，再人工拼凑（容斥思路）

3.有了前缀后缀树，妈妈再也不用担心一个串往前插入字符怎么匹配了！