后缀自动机挺好毒瘤的题。

我们考虑哪些切点是不合法的。肯定是所有的匹配串都被切了。

我们考虑第一个切口的位置。

当第一个切口在第一个出现位置前时，第二个切口必须切掉所有的串。

当第一个切口在$l_{i}$和$l_{i+1}$间的时候(此时必须保证切掉第一个串)，第二个切口必须切掉$s_{i+1}$到$s_{cnt}$这些串

当第一个切口在$l_{cnt}$后时(此时依旧需要保证切掉第一个串)，第二个切口随便放。

于是我们将询问离线，对于每个询问通过在parent树上倍增来找到所对应的节点。

对于后缀自动机上每个节点，通过平衡树启发式合并来维护他的right集合，之后我们只需要维护$\sum{(l_{i+1}-l_{i}) \cdot (r_{i+1}-l_{cnt})}$即可，然后拆开式子，就是$\sum{(r_{i+1}-r_{i}) \cdot r_{i+1}}$和$\sum{r_{i+1}-r_{i}}$。

因为每个询问的长度不同，又因为我们在上述第二三种情况都需要保证切掉第一个串，所以我们所需要提取的区间也不同，这个我们直接在平衡树上乱搞一下就可以了。

之后我们就可以愉快的AC掉这道好毒瘤题啦！

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #define N 100500 8 #define LL long long 9 using namespace std; 10 11 int n,m; 12 char s[N]; 13 struct data{ 14 int l,r; 15 LL ans; 16 }d[300500]; 17 vector 
            
              V[N<<1]; 18 19 #define siz(_) ((!(_))?(0):((_)->size)) 20 #define tp pair
             
               21 struct Treap{ 22 Treap *ch[2]; 23 int key,size,val,maxn,minn,val2,sum2; 24 LL val1,sum1; 25 //sum1=(r[i+1]-r[i])*r[i+1]; 26 //sum2=(r[i+1]-r[i]); 27 Treap(int x){ 28 val=maxn=minn=x; 29 key=rand();size=1; 30 sum1=val1=sum2=val2=0; 31 ch[0]=ch[1]=NULL; 32 } 33 void pushup(){ 34 size=siz(ch[0])+siz(ch[1])+1; 35 minn=maxn=val; 36 sum1=val1;sum2=val2; 37 if(ch[0]){ 38 minn=ch[0]->minn; 39 sum1+=ch[0]->sum1; 40 sum2+=ch[0]->sum2; 41 } 42 if(ch[1]){ 43 maxn=ch[1]->maxn; 44 sum1+=ch[1]->sum1; 45 sum2+=ch[1]->sum2; 46 } 47 } 48 }*root[N<<1]; 49 50 Treap *merge(Treap *a,Treap *b){ 51 if(!a)return b; 52 if(!b)return a; 53 if(a->key<=b->key){ 54 a->ch[1]=merge(a->ch[1],b); 55 a->pushup();return a; 56 } 57 else{ 58 b->ch[0]=merge(a,b->ch[0]); 59 b->pushup();return b; 60 } 61 } 62 tp split(Treap *a,int k){ 63 if(!a)return tp(NULL,NULL); 64 tp x; 65 if(siz(a->ch[0])>=k){ 66 x=split(a->ch[0],k); 67 a->ch[0]=x.second; 68 a->pushup();x.second=a; 69 } 70 else{ 71 x=split(a->ch[1],k-siz(a->ch[0])-1); 72 a->ch[1]=x.first; 73 a->pushup();x.first=a; 74 } 75 return x; 76 } 77 int getrank(Treap *rt,int x){ 78 int k=0; 79 while(1){ 80 if(!rt)return k; 81 if(rt->val
              
               ch[0])+1,rt=rt->ch[1]; 82 else rt=rt->ch[0]; 83 } 84 } 85 void insert(Treap *&rt,int x){ 86 int k=getrank(rt,x); 87 tp t=split(rt,k); 88 Treap *now=new Treap(x); 89 if(t.first){ 90 tp w=split(t.first,k-1); 91 now->val1=now->sum1=1ll*(x-w.second->val)*x; 92 now->val2=now->sum2=(x-w.second->val); 93 t.first=merge(w.first,w.second); 94 } 95 if(t.second){ 96 tp w=split(t.second,1); 97 w.first->val1=w.first->sum1=1ll*(w.first->val-x)*w.first->val; 98 w.first->val2=w.first->sum2=(w.first->val-x); 99 t.second=merge(w.first,w.second);100 }101 rt=merge(merge(t.first,now),t.second);102 }103 void dfs(Treap *o,Treap *&rt){104 if(!o)return ;105 dfs(o->ch[0],rt);106 insert(rt,o->val);107 dfs(o->ch[1],rt);108 }109 int find1(Treap *rt,int x){110 if(rt==NULL)return 0;111 if(rt->val>=x)return find1(rt->ch[0],x);112 else{113 if(!rt->ch[1]||rt->ch[1]->minn>=x)return rt->val;114 return find1(rt->ch[1],x);115 }116 }117 int find2(Treap *rt,int x){118 if(rt==NULL)return 0;119 if(rt->val<=x)return find2(rt->ch[1],x);120 else{121 if(!rt->ch[0]||rt->ch[0]->maxn<=x)return rt->val;122 return find2(rt->ch[0],x);123 }124 }125 void query(Treap *rt,int x,LL &s1,int &s2){126 if(!rt)return ;127 if(rt->val<=x){128 if(rt->ch[0])s1+=rt->ch[0]->sum1,s2+=rt->ch[0]->sum2;129 s1+=rt->val1,s2+=rt->val2;130 query(rt->ch[1],x,s1,s2);131 }132 else query(rt->ch[0],x,s1,s2);133 }134 LL query(int x,int l){135 LL ans=0;136 int r1=root[x]->minn,r2=root[x]->maxn;137 if(r2-l+1
               
                pos1){149 ans+=sum2-sum1;150 ans-=1ll*(r2-l+1)*(size2-size1);151 if(pos2-l+1>r1)ans-=1ll*((pos2-l+1)-r1)*(pos2-(r2-l+1));152 }153 return ans;154 }155 int last[N],tot,mx[N<<1],ch[N<<1][11],par[N<<1];156 157 void extend(int x,int c){158 int p=last[x-1],np=++tot;159 mx[np]=mx[p]+1;160 root[np]=NULL;161 insert(root[np],x);162 for(;p&&!ch[p][c];p=par[p])ch[p][c]=np;163 if(!p) par[np]=1;164 else{165 int q=ch[p][c];166 if(mx[q]==mx[p]+1)par[np]=q;167 else{168 int nq=++tot;169 par[nq]=par[q];170 memcpy(ch[nq],ch[q],sizeof ch[nq]);171 mx[nq]=mx[p]+1;172 root[nq]=NULL;173 par[q]=par[np]=nq;174 for(;p&&ch[p][c]==q;p=par[p])ch[p][c]=nq;175 }176 }177 last[x]=np;178 }179 int e=1,head[N<<1];180 struct edge{181 int v,next;182 }ed[N<<1];183 void add(int u,int v){184 ed[e].v=v;ed[e].next=head[u];185 head[u]=e++;186 }187 int fa[N<<1][22];188 void dfs(int x,int d){189 for(int i=1;(1<
                
                 <=d;i++)190 fa[x][i]=fa[fa[x][i-1]][i-1];191 for(int i=head[x];i;i=ed[i].next){192 fa[ed[i].v][0]=x;193 dfs(ed[i].v,d+1);194 }195 }196 int find(int x,int l){197 for(int i=17;~i;i--)198 if(mx[fa[x][i]]>=l)x=fa[x][i];199 return x;200 }201 void dfs(int x){202 for(int i=head[x];i;i=ed[i].next){203 dfs(ed[i].v);204 if(siz(root[ed[i].v])>siz(root[x]))swap(root[x],root[ed[i].v]);205 dfs(root[ed[i].v],root[x]);206 }207 for(int i=0;i