以前做过一个类似的，但是查询的子串长度最多是10，这个时候就是用bit +　ｈａｓｈ做了。这是因为改变一个字符，只需改变它后面１０个的ｈａｓｈ值就够了，多余的不影响，因为查询去不到那里。（只记得是今年的网络赛来的）

但是这题查询只给了一个长度总和，没上一题好做。

 

这题的思路应该是用bitset查询。

把各个字母拆成不同的bitset，比如abc，拆成

a: 001

b: 010

c: 100

然后，a & (b >> 1) & (c >> 2)即可。

 

最后统计bitset的L + lent - 1，R区间中有多少个1，这里需要用移位加速，不然TLE.

 

bitset的第0位，是最右边的。这也刚好， 相当于把整个串反转了    >> 后也可以把不需要的剔除

 

>> L位，是把左边的无关字符去掉

>> (R - L + 2 - lent)位是可以算出来的

具体就是，从L开始，假设有x位是合法的贡献，那么有L + x - 1 + lent - 1 = R

 

#include 
      
       #define IOS ios::sync_with_stdio(false)using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;const int MAXN = 1e5 + 2;bitset
       
         f[27];char str[MAXN];char t[MAXN];bitset
        
          getAns;void work() {    scanf("%s", str + 1);    int lenstr = strlen(str + 1);    for (int i = 1; i <= lenstr; ++i) f[str[i] - 'a'][i] = 1;    int q;    scanf("%d", &q);    while (q--) {        int op;        scanf("%d", &op);        if (op == 1) {            int pos;            scanf("%d%s", &pos, t);            f[str[pos] - 'a'][pos] = 0;            str[pos] = t[0];            f[str[pos] - 'a'][pos] = 1;        } else {            int L, R;            scanf("%d%d%s", &L, &R, t + 1);            int lent = strlen(t + 1);            if (lent > R - L + 1) {                printf("0\n");                continue;            }            getAns.reset();            getAns = ~getAns;            for (int i = 1; i <= lent; ++i) {                getAns &= (f[t[i] - 'a'] >> (i - 1));            }//            cout << getAns << endl;            getAns >>= L;//            cout << getAns << endl;            int ans = getAns.count();            getAns >>= (R - L + 2 - lent);//            cout << getAns << endl;            ans -= getAns.count();            printf("%d\n", ans);        }    }}int main() {#ifdef local    freopen("data.txt", "r", stdin);//    freopen("data.txt", "w", stdout);#endif    work();    return 0;}