题目概述

给出一个长度为 $n$ 的字符串和一个长度为 $n$ 的序列 $\{a_n\}$，问有多少个子串 $s_{[L,R]}$ 满足 $Rank(s_{[L,R]})=\sum_{i=L}^{R}a_i$ ，其中 $Rank(S)$ 表示 $S$ 在所有子串中的降序排名（重复不算）。

解题报告

一个串的后缀树就是把所有后缀插入Trie，压缩所有没有分支的链后得到的树。每个节点记录的信息有 $fa$ 和 $MAX$ ，分别表示该节点的父亲以及该节点所代表的子串中长度最大的子串的长度。

怎么构造后缀树？定理：一个串反串的后缀自动机的Parent树就是该串的后缀树。当然我不会证明QAQ，我们来感性理解(瞎扯)一下吧：后缀自动机每个节点记录的是Right集合和MAX，而后缀树节点记录的是开头位置和MAX，所以反串的后缀自动机就是后缀树啦2333。或者你可以去学UKK，代码好像有100+行。

那么我们可以这么建后缀树：先建出反串的后缀自动机，然后根据Parent树对后缀树进行连边。

后缀树有一堆性质，估计以后做题会慢慢提到吧QAQ，当然很多性质是和后缀自动机共有的。

这个降序排名看着好奇怪啊，答案保证小于等于 $n$ 也好奇怪啊，难不成……

由于降序排名，所以起点固定时长度越长排名越小，而 $\{a_n\}$ 起点固定时长度越长加和越大，那么很明显每个起点至多只会有一个终点满足排名等于加和。

所以我们可以枚举起点，二分终点，在后缀树里查询出子串排名，然后验证就行了。

但是怎么查询？后缀树虽然缩过了，但是还是满足后缀Trie的性质的，也就是说尽量走小的边得出来的DFS序就完成了子串排序。由于题目要求排名时只算本质不同的，所以每个节点计算时还要减掉父亲的MAX，这和后缀自动机类似。那么查询时只需要找到起点对应的后缀在后缀树里的节点，倍增找满足条件的父亲然后算一下贡献就可以了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
typedef long long LL;
const int maxn=200000,maxt=maxn<<1,Log=19;

int n,sum[maxn+5],fa[maxt+5][Log+5],ti,who[maxt+5];char s[maxn+5];LL rk[maxt+5];
int si=1,pos[maxn+5],ID[maxt+5],son[maxt+5][26],MAX[maxt+5];pair<int,int> ans[maxn+5];

namespace SAM{
    int ro=1,p=1,son[maxt+5][26],fa[maxt+5];
    inline void Extend(int w,int i){
        int np=++si;pos[i]=np;ID[np]=i;MAX[np]=MAX[p]+1;while (p&&!son[p][w]) son[p][w]=np,p=fa[p];
        if (!p) fa[np]=ro; else{
            int q=son[p][w];if (MAX[p]+1==MAX[q]) fa[np]=q; else{
                int nq=++si;ID[nq]=ID[q];MAX[nq]=MAX[p]+1;memcpy(son[nq],son[q],sizeof(son[q]));
                fa[nq]=fa[q];fa[np]=fa[q]=nq;while (p&&son[p][w]==q) son[p][w]=nq,p=fa[p];
            }
        }p=np;
    }
}
void Dfs(int x,int pre=0){
    fa[x][0]=pre;for (int i=1;i<=Log;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    who[++ti]=x;for (int i=0;i<26;i++) if (son[x][i]) Dfs(son[x][i],x);
}
inline void MakeST(){
    for (int i=2;i<=si;i++) son[SAM::fa[i]][s[ID[i]+MAX[SAM::fa[i]]]-'a']=i;Dfs(1);
    for (int i=si;i;i--) rk[who[i]]=rk[who[i+1]]+MAX[who[i+1]]-MAX[SAM::fa[who[i+1]]];
}
inline LL Rank(int L,int R){
    R=R-L+1;L=pos[L];for (int i=Log;~i;i--) if (MAX[fa[L][i]]>=R) L=fa[L][i];
    return rk[L]+MAX[L]-R+1;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%s",s+1);n=strlen(s+1);for (int i=1;i<=n;i++) scanf("%d",&sum[i]),sum[i]+=sum[i-1];
    for (int i=n;i;i--) SAM::Extend(s[i]-'a',i);MakeST();int tot=0;
    for (int i=1;i<=n;i++){
        int L=i,R=n,tem=0;
        for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)){
            LL now=Rank(i,mid);if (now==sum[mid]-sum[i-1]) {tem=mid;break;}
            now<sum[mid]-sum[i-1]?R=mid-1:L=mid+1;
        }
        if (tem) ans[++tot]=mp(i,tem);
    }
    sort(ans+1,ans+1+tot);printf("%d\n",tot);
    for (int i=1;i<=tot;i++) printf("%d %d\n",ans[i].fr,ans[i].sc);
    return 0;
}