字符串水题
题目链接：luogu U138101
题目大意
给你一个大字符串，然后每次给你一个小字符串和 l,r，问你有多少个小字符串的子串满足它是大字符串的子串，而且它每个字符作为数字之和在 l~r 之间。
（保证字符串都是由数字构成）
思路
首先不难看出首先可以 SAM 或者 SA（这个要把所有字符串拼在一起然后搞 RMQ） 求出以小串每个位置为右端点，它左端点最左可以是多少都在大串里面有值。
然后不难看出，它这个左端点的位置肯定是递增的。
简单证明：假设 (i) 为右端点的时候最左的左端点是 (x)，如果 (i+1) 的时候左端点 (<x)，则有 (x-1sim i+1) 是大串的子串，那 (x-1sim i) 一定是大串的子串，那 (i) 为右端点时的最左左端点就应该是 (x-1) 而不是 (x)，矛盾。
那我们接下来就是要考虑这些区间中有多少个的值是在 (lsim r) 之中的。
考虑先搞出每个小字符串值的前缀和，然后假设你现在的右端点是 (y)，你就要找到满足的位置 (x)，使得 (lleqslant s_y-s_xleqslant r)。
然后我们发现右端点每次固定，那化简：
(s_xleqslant s_y-l,s_xgeqslant s_y-r)
就是 (s_y-rleqslant s_xleqslant s_y-l)
发现这是区间查询，考虑用树状数组来搞。
然后由于左端点递增，你左端点只会一直往右移，你就只需要取消贡献。
然后每次右端点右移你就加入贡献。
然后就好啦。
代码
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int sn, q, l, r, an, b[200001];
char s[200001], a[200001];
struct Tree {//树状数组
int t[1800002];
void insert(int x, int y) {
for (; x <= 9 * sn + 1; x += x & (-x))
t[x] += y;
}
int ask(int x) {
int re = 0;
for (; x; x -= x & (-x))
re += t[x];
return re;
}
int query(int l, int r) {
if (l < 1) l = 1;
if (l > r) return 0;
return ask(r) - ask(l - 1);
}
}T;
struct SAM {//SAM
int lst, tot;
struct node {
int len, fa, son[26];
node() {
len = fa = 0;
memset(son, 0, sizeof(son));
}
}d[800001];
void insert(int c, int op) {
int p = lst;
int np = ++tot;
lst = np;
d[np].len = d[p].len + 1;
for (; p && !d[p].son[c]; p = d[p].fa)
d[p].son[c] = np;
if (!p) d[np].fa = 1;
else {
int q = d[p].son[c];
if (d[q].len == d[p].len + 1) d[np].fa = q;
else {
int nq = ++tot;
d[nq] = d[q];
d[nq].len = d[p].len + 1;
d[q].fa = d[np].fa = nq;
for (; p && d[p].son[c] == q; p = d[p].fa)
d[p].son[c] = nq;
}
}
}
void build() {
tot = lst = 1;
for (int i = 0; i < sn; i++)
insert(s[i] - '0', 1);
}
ll gogo() {
ll re = 0;
int now = 1, len = 0, nowt = 1;
for (int i = 1; i <= an; i++) {//枚举右端点
if (d[now].son[a[i] - '0']) now = d[now].son[a[i] - '0'], len++;//求出左端点的最左范围
else {
for (; now && !d[now].son[a[i] - '0']; now = d[now].fa) ;
if (!now) now = 1, len = 0;
else len = d[now].len + 1, now = d[now].son[a[i] - '0'];
}
while (nowt <= i - len) {//左端点往右移动
T.insert(b[nowt - 1] + 1, -1);
nowt++;
}
T.insert(b[i - 1] + 1, 1);//右端点移动一格
re += 1ll * T.query(b[i] - r + 1, b[i] - l + 1);//计算
}
for (int i = nowt; i <= an; i++)//清空
T.insert(b[i - 1] + 1, -1);
return re;
}
}S;
int main() {
scanf("%s", &s);
sn = strlen(s);
S.build();
scanf("%d", &q);
for (int qq = 1; qq <= q; qq++) {
scanf("%s", a + 1); scanf("%d %d", &l, &r);
an = strlen(a + 1);
for (int i = 1; i <= an; i++)//求出来数前缀和
b[i] = a[i] - '0' + b[i - 1];
printf("%lld
", S.gogo());
}
return 0;
}