题意
你有一个字符串，你需要支持两种操作：
1：在字符串的末尾插入一个字符 (c)
2：询问当前字符串的 ([l,r]) 子串中的不同子串个数
为了加大难度，操作会被加密（强制在线）。
(n,mle 50000)，空间 ( ext{1GB})
题解
原题好像是【北京集训 2017 String】，题意：给你一个模板串 (T)，有 (Q) 组询问，每组询问给出 (2) 个正整数 (l,r)，请你找出 (T[l...r]) 中出现至少 (2) 次的最长子串。(|T|,Qle 10^5)。（这题以前欧神好像让 gdc 写过）
subtask 1（(n,mle 1500)）
直接建一个后缀自动机暴力跑查询 好像是 (O(n^3)) 的（本文假设 (n,m,n+m) 同阶）……
如果你刚学 SAM 的话，可以想到对字符串建 (n) 个 SAM，第 (i) 个 SAM 插入字符串的第 (i) 到 (n) 位，这样第 (i) 个 SAM 就可以预处理出 ([i,i],[i,i+1],cdots,[i,n]) 这些询问区间。考虑在线操作，对于插入，设字符串当前长度为 (len)，则需要对 (len) 个后缀自动机 ( ext{extend}) 一位字符，并更新 (len) 个区间的答案；对于查询，(O(1)) 取预处理的答案即可。
时间复杂度 (O(n^2))，空间复杂度 (O(26n^2))，如果 SAM 不动态开点，请把所有变量开成 ( ext{short})，开成 ( ext{int}) 或 ( ext{long long}) 会被卡空间。
subtask 2（离线）
鸽了（看完在线做法你大概也猜到离线做法了）
subtask all
不难发现这题的操作 1 就是 ( ext{SAM}) 的 ( ext{extend}) 过程。
设进行一次 1 操作后字符串的长度为 (len)，则当次 ( ext{extend}) 会使字符串增加以第 (len) 位为结尾的所有子串。
这些子串对应的就是 ( ext{SAM}) 的 ( ext{parents}) 树上一个叶子节点到根的链，且那个叶子节点就是你新建的表示子串 (S_{1cdots len}) 的节点。
于是我们考虑用 ( ext{LCT}) 动态维护 ( ext{SAM}) 的 ( ext{parents}) 树。
但有个问题：哪些点放在同一条重链上（同一个 ( ext{splay}) 中）呢？
这个问题似乎不太好想，我们先跳过。
我们考虑如何维护某个区间 ([l,r]) 中的不同子串数量。
这个问题可以简化为给你 (n) 个数，每次询问某个区间 ([l,r]) 中有多少个不同的数。
显然可以使用容斥法，用总数量减去那些非最后一次出现的数。考虑预处理答案，从前往后依次加入每个数，加入第 (i) 个数即将主席树的第 (i) 个版本的第 (i) 位加 (1)。若该数在之前出现过，设上一次出现的位置为 (lst)，则在主席树的第 (i) 个版本的第 (j) 位减 (1)。
那么区间内不同子串数量也可以类似地用主席树解决。
考虑暴力，做法类似前一题：考虑 ( ext{extend}) 到第 (len) 位时，检查所有以第 (len) 位为结尾的子串是否在之前出现过，若出现过，设这个子串上一次出现位置的左端点为 (x)，则对于所有 (rge len,space lle x) 的询问，答案要从子串总数中 (-1)，放到主席树上 就是主席树的第 (len) 个版本的第 (x) 位减 (1)。
我们之前说过，所有以第 (len) 位为结尾的子串 是 ( ext{parents}) 树上的一条链。在 ( ext{LCT}) 上取一条链的信息 是经典操作，而且这里的链顶就是根，所以我们只要把链底节点 ( ext{access}) 一下就行了。在 ( ext{access}) 时我们需要链上每个点上一次出现的位置 (lst)，由于一条重链上所有点的 (lst) 相同，故 ( ext{access}) 后在链顶打个 (tag)，下次访问这条链时 ( ext{pushdown}) 即可。有了每个点的 (lst)，我们就可以在 ( ext{access}) 时对每个点在主席树上进行修改。查询区间 ([l,r]) 的答案时，对主席树的第 (r) 个版本的 ([l,r]) 区间求和即可。
由此可知，( ext{LCT}) 中一条重链存的是所有上一次出现位置相同的 SAM 节点。
然后就是码码码了。
注意这题的主席树是区间修改，所以每新建一个版本最多会增加 (4log n) 个点而不是 (log n) 个点，所以主席树大小要开到 (80n) 而不是 (20n)。
复杂度 (O(nlog^2 n))。
（我）翻车的一个地方：访问 (x) 号点时，一定要把它所在的重链顶端的 (tag) ( ext{pushdown}) 到 (x) 号点的儿子，即 (x) 号点要 ( ext{pushdown})！
（好吧其实是个傻逼错误，那大家无视好了）
#include<bits/stdc++.h>
#define ll long long
#define N 200005
using namespace std;
inline int read(){
int x=0; bool f=1; char c=getchar();
for(;!isdigit(c); c=getchar()) if(c=='-') f=0;
for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
if(f) return x; return 0-x;
}
int n,m,len;
char s[50001];
int rt[N];
namespace PT{
struct Tree{int l,r,tag; ll sum;}tr[N*80];
int cnt=0;
void mdf(int& o, int l, int r, int L, int R, int v){
tr[++cnt]=tr[o], o=cnt;
tr[o].sum += (ll)(min(r,R)-max(l,L)+1) * v;
if(L<=l && r<=R){tr[o].tag+=v; return;}
int mid=l+r>>1;
if(L<=mid) mdf(tr[o].l,l,mid,L,R,v);
if(R>mid) mdf(tr[o].r,mid+1,r,L,R,v);
}
ll query(int o, int l, int r, int L, int R){
if(!o) return 0;
if(L<=l && r<=R) return tr[o].sum;
int mid=l+r>>1; ll res = (ll)(min(r,R)-max(l,L)+1) * tr[o].tag;
if(L<=mid) res+=query(tr[o].l,l,mid,L,R);
if(R>mid) res+=query(tr[o].r,mid+1,r,L,R);
return res;
}
}
namespace LCT{
int son[N][2],fa[N],len[N],lst[N],tag[N],stk[N],top;
inline bool isRoot(int x){return son[fa[x]][0]!=x && son[fa[x]][1]!=x;}
inline bool idf(int x){return son[fa[x]][1]==x;}
inline void mark(int x, int y){lst[x]=tag[x]=y;}
void pushdown(int x){
if(tag[x]){
if(son[x][0]) mark(son[x][0],tag[x]);
if(son[x][1]) mark(son[x][1],tag[x]);
tag[x]=0;
}
}
inline void connect(int x, int f, int fx){
fa[x]=f, son[f][fx]=x;
}
void rotate(int x){
int y=fa[x], z=fa[y], idf_x=idf(x), idf_y=idf(y), B=son[x][idf_x^1];
if(!isRoot(y)) connect(x,z,idf_y);
else fa[x]=z;
connect(B,y,idf_x), connect(y,x,idf_x^1);
}
void splay(int x){
stk[top=1]=x;
for(int i=x; !isRoot(i); i=fa[i]) stk[++top]=fa[i];
for(; top; --top) pushdown(stk[top]);
while(!isRoot(x)){
int f=fa[x];
if(!isRoot(f)) rotate(idf(f)==idf(x) ? f : x);
rotate(x);
}
}
void access(int x, int id){
for(int y=0; ; x=fa[y=x]){
splay(x);
if(lst[x]) PT::mdf(rt[id],1,n,lst[x]-len[x]+1,lst[x]-len[fa[x]],1);
son[x][1]=y;
if(!fa[x]) break;
}
mark(x,id);
}
inline int get(int x){splay(x); return lst[x];}
void link(int x, int y){splay(x), fa[x]=y;}
}
namespace SAM{
int ch[N][26],fa[N],len[N],tot,lst;
inline void init(){tot=lst=1;}
void extend(int c, int id){
int u=lst, v=++tot; len[v]=len[u]+1, LCT::len[v]=len[v];
for(; u && !ch[u][c]; u=fa[u]) ch[u][c]=v;
if(!u) fa[v]=1, LCT::link(v,1), LCT::access(v,id);
else{
int w=ch[u][c];
if(len[w]==len[u]+1) fa[v]=w, LCT::link(v,w), LCT::access(v,id);
else{
int t=++tot; len[t]=len[u]+1, LCT::len[t]=len[t], LCT::lst[t]=LCT::get(w);
memcpy(ch[t],ch[w],sizeof ch[w]);
fa[t]=fa[w], fa[w]=fa[v]=t;
LCT::link(t,fa[t]), LCT::link(v,t), LCT::access(v,id), LCT::link(w,t);
for(; u && ch[u][c]==w; u=fa[u]) ch[u][c]=t;
}
}
lst=v;
}
}
int main(){
int type=read();
scanf("%s",s+1), len=strlen(s+1);
m=read();
n=len+m;
SAM::init();
for(int i=1; i<=len; ++i) rt[i]=rt[i-1], SAM::extend(s[i]-'a',i);
int opt; ll l,r,ans=0; char c[1];
while(m--){
opt=read();
if(opt==1){
scanf("%s",c);
++len, rt[len]=rt[len-1];
SAM::extend(((ll)c[0]-'a'+ans*type)%26, len);
}
else{
l = ((ll)read()-1+ans*type) % len + 1, r = ((ll)read()-1+ans*type) % len + 1;
printf("%lld
", ans = (ll)(r-l+2)*(r-l+1)/2 - PT::query(rt[r],1,n,l,r));
}
}
return 0;
}