#P9712. 麻烦的杂货店

    ID: 6336 传统题 5000ms 512MiB 尝试: 1 已通过: 1 难度: 7 上传者: 标签>CF2300提高+/省选-一维前缀和栈线性 DPST 表幂等运算区间覆盖

麻烦的杂货店

题目描述

一家杂货店卖一种零食,每袋 5 元。某天编号在区间 [l,r][l,r] 内的小学生按编号递增的顺序依次来店。每人只买一袋,并且只有一张固定面额的钞票。商店开门时没有零钱,只能用已经收到的 5 元钞票为付 10 元的人找零。关门时,收到的 5 元钞票必须全部用完。

店主可以选择只接待 [l,r][l,r] 内某个连续子区间的学生。她也可以当天一袋都不卖。求每天最多能卖出多少袋。

输入格式

第一行两个整数 N,MN,M,分别是学生人数和天数。第二行一个长为 NN 的字符串。第 ii 个字符为 F 表示编号 ii 的学生只有 5 元,为 T 表示只有 10 元。

接下来 MM 行,每行两个整数 li,ril_i,r_i,表示第 ii 天来店学生的编号范围。

输出格式

输出 MM 行。第 ii 行是第 ii 天能卖出的最大袋数。

样例

6 9
FTFTFT
1 2
3 4
5 6
1 4
3 6
1 6
1 3
1 4
1 5
2
2
2
4
4
6
2
4
4

原 PDF 输出行数中的 NN 为笔误,按天数 MM 输出。样例和本站评测均按此规则。

数据范围

1≤N≤1051\le N\le10^5,1≤M≤4×1061\le M\le4\times10^6,1≤li≤ri≤N1\le l_i\le r_i\le N。

对于 20% 的数据,N,M≤400N,M\le400。对于 40% 的数据,N,M≤4000N,M\le4000。对于 80% 的数据,M≤105M\le10^5。

原题面 PDF