数据假了。

这是开了 long long 之后的 std：https://www.luogu.com.cn/record/86403797

#include<bits/stdc++.h>
#define int long long
#define MAXN 500010
#define MAXM 1000010
#define lson now << 1
#define rson now << 1 | 1
using namespace std;
struct state{
    int len, link;
    map<char, int> nxt;
};
struct node{
    int l, r;
    int num, val, sum, lazy_tag;
};
struct edge{
    int pre, to;
};
edge e[MAXM];
node tree[MAXM << 2];
state sam[MAXM];
int n, q, cnt, tot, last, times;
int head[MAXM], book[MAXM], deep[MAXM], val[MAXM], num[MAXN], deg[MAXM], top[MAXM], son[MAXM], low[MAXM], siz[MAXM], id[MAXM], fa[MAXM], dp[MAXM];
char s[MAXN], t[MAXN];

// 构造后缀自动机( SAM )
void sam_init(){
    sam[0].len = 0;
    sam[0].link = -1;
    last = 0;
}
void sam_extend(char c){
    int now = ++tot;
    dp[now] = 1;
    sam[now].len = sam[last].len + 1;
    int p = last;
    while(p != -1 && !sam[p].nxt.count(c)){
        sam[p].nxt[c] = now;
        p = sam[p].link;
    }
    if(p == -1) sam[now].link = 0;
    else{
        int q = sam[p].nxt[c];
        if(sam[p].len + 1 == sam[q].len) sam[now].link = q;
        else{
            int clone = ++tot;
            sam[clone] = (state){sam[p].len + 1, sam[q].link, sam[q].nxt};
            while(p != -1 && sam[p].nxt[c] == q){
                sam[p].nxt[c] = clone;
                p = sam[p].link;
            }
            sam[q].link = sam[now].link = clone;
        }
    }
    last = now;
}

// 找出字符串 s 在 SAM 中对应的节点
int find(char *s){
    int len = strlen(s), now = 0;
    for(int i = 0; i < len; i++){
        if(!sam[now].nxt.count(s[i])) return -1;
        now = sam[now].nxt[s[i]];
    }
    return now;
}

// 构建 parent 树
void add_edge(int u, int v){
    e[++cnt].pre = head[u];
    e[cnt].to = v;
    head[u] = cnt;
}

// 在 parent 树上 DP，求出当前节点对应的等价类在原字符串中出现的次数
void dfs(int now){
    for(int i = head[now]; i; i = e[i].pre){
        dfs(e[i].to);
        dp[now] += dp[e[i].to];
    }
}

// 树链剖分预处理
void dfs1(int now){
    siz[now] = 1;
    for(int i = head[now]; i; i = e[i].pre){
        deep[e[i].to] = deep[now] + 1;
        dfs1(e[i].to);
        siz[now] += siz[e[i].to];
        if(son[now] == 0 || siz[e[i].to] > siz[son[now]]) son[now] = e[i].to;
    }
}
void dfs2(int now, int fr){
    id[now] = ++times; top[now] = fr; book[times] = now;
    if(son[now] == 0){
        low[now] = id[now];
        return ;
    }
    dfs2(son[now], fr);
    low[now] = max(low[now], low[son[now]]);
    for(int i = head[now]; i; i = e[i].pre){
        if(e[i].to == son[now]) continue;
        dfs2(e[i].to, e[i].to);
        low[now] = max(low[now], low[e[i].to]);
    }
}

// 线段树部分
void push_up(int now){
    tree[now].sum = tree[lson].sum + tree[rson].sum;
    tree[now].val = tree[lson].val + tree[rson].val;
    tree[now].num = tree[lson].num + tree[rson].num;
}
void push_down(int now){
    if(tree[now].lazy_tag != 0){
        tree[lson].val += tree[now].lazy_tag;
        tree[rson].val += tree[now].lazy_tag;
        tree[lson].val += (tree[lson].r - tree[lson].l + 1) * tree[now].lazy_tag;
        tree[rson].val += (tree[rson].r - tree[rson].l + 1) * tree[now].lazy_tag;
        tree[lson].sum += tree[lson].num * tree[now].lazy_tag;
        tree[rson].sum += tree[rson].num * tree[now].lazy_tag;
        tree[now].lazy_tag = 0;
    }
}
void build(int now, int l, int r){
    tree[now].l = l; tree[now].r = r;
    if(tree[now].l == tree[now].r){
        tree[now].val = 1;
        tree[now].num = dp[book[r]] * (sam[book[l]].len - sam[sam[book[l]].link].len);
        tree[now].sum = tree[now].num * tree[now].val;
        return ;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    build(lson, l, mid); build(rson, mid + 1, r);
    push_up(now);
}
void update(int now, int l, int r, int x){
    if(tree[now].l >= l && tree[now].r <= r){
        tree[now].lazy_tag += x;
        tree[now].val += (tree[now].r - tree[now].l + 1) * x;
        tree[now].sum += tree[now].num * x;
        return ;
    }
    push_down(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(r <= mid) update(lson, l, r, x);
    else if(l > mid) update(rson, l, r, x);
    else update(lson, l, mid, x), update(rson, mid + 1, r, x);
    push_up(now);
}
int query(int now, int l, int r){
    if(tree[now].l >= l && tree[now].r <= r){
        return tree[now].sum;
    }
    push_down(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if(r <= mid) return query(lson, l, r);
    else if(l > mid) return query(rson, l, r);
    else return query(lson, l, mid) + query(rson, mid + 1, r);
}
signed main(){
    scanf("%lld%lld%s",&n,&q,s + 1);
    sam_init();
    for(int i = 1; i <= n; i++) sam_extend(s[i]);
    for(int i = 1; i <= tot; i++) add_edge(sam[i].link, i);
    dfs(0); dfs1(0); dfs2(0, 0); build(1, 1, tot + 1);
    for(int i = 1; i <= q; i++){
        int op, p;
        scanf("%lld%s",&op, t);
        p = find(t);
        if(op == 0){
            printf("%lld\n",query(1, id[p], low[p]));
        }else{
            int x; scanf("%lld",&x);
            if(x<0) puts("Qing WA");
            update(1, id[p], low[p], x);
        }
    }
    return 0;
}