A2035 | 背单词
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
小明对英语一窍不通，令老师十分头疼。于是期末考试前夕，小明被逼着开始背单词……
老师给了小明一篇长度为N的英语文章，然后让小明背M个单词。为了确保小明不会在背单词时睡着，老师会向他提Q个问题，每次老师随机选择一个区间L..R，小明要回答在这段文字中他背过的单词总共出现过多少次。
老师给了小明一篇长度为N的英语文章，然后让小明背M个单词。为了确保小明不会在背单词时睡着，老师会向他提Q个问题，每次老师随机选择一个区间L..R，小明要回答在这段文字中他背过的单词总共出现过多少次。
输入格式
第一行两个整数M、Q如前所述。第二行为英语文章。接下来M行每行一个需要背的单词。接下来Q行每行一个询问，包含两个整数L、R（含端点），即给定的文字区间。
输出格式
Q行，对每个询问输出一行表示答案。
输入输出样例
输入 #1
3 3 abcabcbc abc bc a 1 3 6 7 1 8
输出 #1
3 0 7
数据范围：
对于30%的数据，1<=N<=10^3,1<=Q<=10^3
对于60%的数据，1<=N<=10^5,1<=Q<=10^5
对于100%的数据，1<=N<=10^6,1<=M<=10,1<=Q<=10^6,1<=每个单词的长度<=N,1<=L<=R<=N
提示：数据较大，请大家尽量采取高效率的读入输出方法。
对于30%的数据，1<=N<=10^3,1<=Q<=10^3
对于60%的数据，1<=N<=10^5,1<=Q<=10^5
对于100%的数据，1<=N<=10^6,1<=M<=10,1<=Q<=10^6,1<=每个单词的长度<=N,1<=L<=R<=N
提示：数据较大，请大家尽量采取高效率的读入输出方法。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？