【LOJ#6041】事情的相似度（后缀自动机）

题面

题解

\(\mbox{YCB}\)搬了这道题目。。。\(\mbox{QwQ}\)

还是用到\(lcp\)就是\(parent\)树上的\(LCA\)的\(len\)。

每次询问显然就是区间内点的贡献。

那么考虑所有可能出现的点对。

显然对于两个子串而言，只会匹配最靠近的两个。

那么用\(set\)维护\(endpos\)集合，每次合并的时候将两个最靠近的位置合并成为一个点对，其贡献就是当前点的\(len\)。

那么最终询问扫描线解决即可。

\(zsy\)还有一种用\(LCT\)的做法，大致口胡一下就是类似上面的操作，要求的就是一个链并。每次将当前点到根节点的路径染色，那么每次的交点就是一个\(LCA\)。发现染色操作类似\(LCT\)的\(access\)，因此直接这么模拟即可。

代码是第一种做法的。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define MAX 100100inline int read(){ int x=0;bool t=false;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x;}int n,m;char ch[MAX];struct Node{int son[26],len,ff;}t[MAX<<1];int last,tot,sum;set
           
             S[MAX<<1];void extend(int id,int c){ int p=last,np=++tot;last=np; t[np].len=t[p].len+1; while(p&&!t[p].son[c])t[p].son[c]=np,p=t[p].ff; if(!p)t[np].ff=1; else { int q=t[p].son[c]; if(t[q].len==t[p].len+1)t[np].ff=q; else { int nq=++tot; t[nq]=t[q];t[nq].len=t[p].len+1; t[np].ff=t[q].ff=nq; while(p&&t[p].son[c]==q)t[p].son[c]=nq,p=t[p].ff; } } S[np].insert(id);}struct Point{int u,v,len;}p[MAX<<5];bool operator<(Point a,Point b){return (a.v!=b.v)?a.v