//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "区间本质不同子串个数": {
        "prefix": "acm-6.6SAM+LCT+线段树",
        "body": [
            "#include<algorithm>",
            "#include<cstring>",
            "#include<cstdio>",
            "#define LL long long",
            "#define Re register int",
            "using namespace std;",
            "const int N=1e5+3,M=2e5+3;",
            "int n,T;LL Ans[M];char s[N];",
            "struct Query{int l,r,id;inline bool operator<(const Query &O)const{return r<O.r;}}Q[M];",
            "inline void in(Re &x){",
            "    int f=0;x=0;char c=getchar();",
            "    while(c<'0'||c>'9')f|=c=='-',c=getchar();",
            "    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();",
            "    x=f?-x:x;",
            "}",
            "struct Segment_Tree{",
            "\t#define pl (p<<1)",
            "\t#define pr (p<<1|1)",
            "\t#define mid ((L+R)>>1)",
            "\tstruct QAQ{LL S,add;}tr[N<<2];",
            "\tinline void updata(Re p,Re L,Re R,LL v){tr[p].add+=v,tr[p].S+=v*(R-L+1);}",
            "\tinline void pushdown(Re p,Re L,Re R){",
            "\t\tif(tr[p].add)updata(pl,L,mid,tr[p].add),updata(pr,mid+1,R,tr[p].add),tr[p].add=0;",
            "\t}",
            "\tinline void change(Re p,Re L,Re R,Re l,Re r,Re v){",
            "\t\tif(l<=L&&R<=r){updata(p,L,R,v);return;}",
            "\t\tpushdown(p,L,R);",
            "\t\tif(l<=mid)change(pl,L,mid,l,r,v);",
            "\t\tif(r>mid)change(pr,mid+1,R,l,r,v);",
            "\t\ttr[p].S=tr[pl].S+tr[pr].S;",
            "\t}",
            "\tinline LL ask(Re p,Re L,Re R,Re l,Re r){",
            "\t\tif(l<=L&&R<=r)return tr[p].S;",
            "\t\tpushdown(p,L,R);LL ans=0;",
            "\t\tif(l<=mid)ans+=ask(pl,L,mid,l,r);",
            "\t\tif(r>mid)ans+=ask(pr,mid+1,R,l,r);",
            "\t\treturn ans;",
            "\t}",
            "\t#undef pl",
            "\t#undef pr",
            "}TR;",
            "struct Suffix_Automaton{",
            "\tint O,last,pos[N],link[N<<1],maxlen[N<<1],trans[N<<1][26];",
            "\tSuffix_Automaton(){last=O=1;}",
            "\tinline void insert(Re ch,Re id){",
            "\t\tRe z=++O,p=last;maxlen[z]=maxlen[p]+1;",
            "\t\twhile(p&&!trans[p][ch])trans[p][ch]=z,p=link[p];",
            "\t\tif(!p)link[z]=1;",
            "\t\telse{",
            "\t\t\tRe x=trans[p][ch];",
            "\t\t\tif(maxlen[x]==maxlen[p]+1)link[z]=x;",
            "\t\t\telse{",
            "\t\t\t\tRe y=++O;maxlen[y]=maxlen[p]+1;",
            "\t\t\t\tfor(Re i=0;i<26;++i)trans[y][i]=trans[x][i];",
            "\t\t\t\twhile(p&&trans[p][ch]==x)trans[p][ch]=y,p=link[p];",
            "\t\t\t\tlink[y]=link[x],link[z]=link[x]=y;",
            "\t\t\t}",
            "\t\t}",
            "\t\tpos[id]=last=z;",
            "\t}",
            "}SAM;",
            "struct Link_Cut_Tree{",
            "\t#define pl (tr[p].ps[0])",
            "\t#define pr (tr[p].ps[1])",
            "\t#define pf (tr[p].fa)",
            "\t#define pv (tr[p].v)",
            "\tint Q[N<<1];",
            "\tstruct QAQ{int v,fa,tag,ps[2];}tr[N<<1];",
            "\tinline void updata(Re p,Re v){tr[p].tag=tr[p].v=v;}",
            "\tinline void pushdown(Re p){",
            "\t\tif(tr[p].tag){",
            "\t\t\tif(pl)updata(pl,tr[p].tag);",
            "\t\t\tif(pr)updata(pr,tr[p].tag);",
            "\t\t\ttr[p].tag=0;",
            "\t\t}",
            "\t}",
            "\tinline int which(Re p){return tr[pf].ps[1]==p;}",
            "\tinline int nort(Re p){return tr[pf].ps[0]==p||tr[pf].ps[1]==p;}",
            "\tinline void connect(Re p,Re fa,Re o){tr[pf=fa].ps[o]=p;}",
            "\tinline void rotate(Re p){",
            "\t\tRe fa=pf,fas=which(p);",
            "\t\tRe pa=tr[fa].fa,pas=which(fa);",
            "\t\tRe x=tr[p].ps[fas^1];",
            "\t\tif(nort(fa))tr[pa].ps[pas]=p;pf=pa;",
            "\t\tconnect(x,fa,fas),connect(fa,p,fas^1);",
            "\t}",
            "\tinline void splay(Re p){",
            "\t\tRe x=p,t=0;Q[++t]=x;",
            "\t\twhile(tr[x].fa)Q[++t]=x=tr[x].fa;",
            "\t\twhile(t)pushdown(Q[t--]);",
            "\t\tfor(Re fa;nort(p);rotate(p))",
            "\t\t\tif(nort(fa=pf))rotate(which(p)==which(fa)?fa:p);",
            "\t}",
            "\tinline void access(Re p,Re r){",
            "\t\tRe son=0;",
            "\t\tfor(;p;son=p,p=pf){",
            "\t\t\tsplay(p);",
            "\t\t\tif(pv)TR.change(1,1,n,pv-SAM.maxlen[p]+1,pv-SAM.maxlen[pf],-1);",
            "\t\t\tpr=son;",
            "\t\t}",
            "\t\tupdata(son,r),TR.change(1,1,n,1,r,1);",
            "\t}",
            "}T1;",
            "int main(){",
            "//    freopen(\"123.txt\",\"r\",stdin);",
            "    scanf(\"%s\",s+1),n=strlen(s+1),in(T);",
            "\tfor(Re i=1;i<=n;++i)SAM.insert(s[i]-'a',i);",
            "\tfor(Re i=2;i<=SAM.O;++i)T1.tr[i].fa=SAM.link[i];",
            "\tfor(Re i=1;i<=T;++i)in(Q[i].l),in(Q[i].r),Q[i].id=i;",
            "    sort(Q+1,Q+T+1);",
            "    for(Re i=1,r=0;i<=T;++i){",
            "    \twhile(r<Q[i].r)++r,T1.access(SAM.pos[r],r);",
            "    \tAns[Q[i].id]=TR.ask(1,1,n,Q[i].l,Q[i].r);",
            "\t}",
            "\tfor(Re i=1;i<=T;++i)printf(\"%lld\\n\",Ans[i]);",
            "}",
            ""
        ],
        "description": "插入 区间本质不同子串个数"
    }
}