http://codeforces.com/contest/914/problem/F

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

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

这题的思路应该是用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 <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int MAXN = 1e5 + ;
bitset<MAXN> f[];
char str[MAXN];
char t[MAXN];
bitset<MAXN> getAns;
void work() {
scanf("%s", str + );
int lenstr = strlen(str + );
for (int i = ; i <= lenstr; ++i) f[str[i] - 'a'][i] = ;
int q;
scanf("%d", &q);
while (q--) {
int op;
scanf("%d", &op);
if (op == ) {
int pos;
scanf("%d%s", &pos, t);
f[str[pos] - 'a'][pos] = ;
str[pos] = t[];
f[str[pos] - 'a'][pos] = ;
} else {
int L, R;
scanf("%d%d%s", &L, &R, t + );
int lent = strlen(t + );
if (lent > R - L + ) {
printf("0\n");
continue;
}
getAns.reset();
getAns = ~getAns;
for (int i = ; i <= lent; ++i) {
getAns &= (f[t[i] - 'a'] >> (i - ));
}
// cout << getAns << endl;
getAns >>= L;
// cout << getAns << endl;
int ans = getAns.count();
getAns >>= (R - L + - 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 ;
}

最新文章

  1. C# Stream
  2. oracle deterministic 关键字
  3. java 面试每日一题7
  4. c# 之五行地支
  5. css规范大全
  6. SpriteParticle II
  7. 判断sqlserver临时表等临时资源是否存在
  8. (转)Phonegap VS AppCan
  9. 自己做个 Tag标签
  10. MySQL show master / slave status 命令参数
  11. 这是您一直期待的所有iOS 11功能的屏幕截图
  12. cnblog 模板 SimpleMemory 个性化设置代码备份
  13. C# ListView应用
  14. 用idea部署maven-web项目
  15. EOS 权限
  16. Postfix 邮件服务 - 邮箱组件 cyrus-sasl
  17. PL/SQL学习笔记之基本块格式与语法
  18. windows环境下搭建Java开发环境(一):jdk安装和配置
  19. HTTP协议GET和POST的区别
  20. oracle数据据 Python+Pandas 获取Oracle数据库并加入DataFrame

热门文章

  1. 监控linux系统的简易脚本
  2. java反射机制的粗略理解
  3. .Net Core Api 使用版本控制
  4. 企业sudo权限规划详解 (实测一个堆命令搞定)
  5. P与NP问题详解
  6. 【图灵学院09】RPC底层通讯原理之Netty线程模型源码分析
  7. Python学习过程(二)
  8. 「杂录」CQOI 2018 背板记
  9. LUNA16数据集(三)预处理
  10. firefox浏览本地网站慢的问题