#P4786. [BalkanOI2018] Election

[BalkanOI2018] Election

题目描述

翻译自 BalkanOI 2018 Day1 T1「Election

有一个长度为 NN 的字符串 S[1N]S[1\dots N],它仅由 CT 两种字母组成。
现在有 QQ 个查询,每个查询包含两个整数 LLRR,表示:设新字符串 S=S[LR]S'=S[L\dots R],至少在 SS' 中要删除多少个字符,才能保证:对于 SS' 的每一个前缀和后缀,其 C 的数量都不小于 T 的数量。

输入格式

第一行有一个整数 NN
第二行有一个长度为 NN 的字符串 SS
第三行有一个整数 QQ
在接下来的 QQ 行中,每行有两个整数 LLRR,表示一组查询。

输出格式

对于每组查询输出一行,表示至少在 SS' 中要删除多少个字符,才能保证题面要求。

11
CCCTTTTTTCC
3
1 11
4 9
1 6
4
6
3

提示

样例解释

查询 1:CCCTTTTTTCC
查询 2:TTTTTT
查询 3:CCCTTT

子任务 #1(28 分):1N,Q20001 ≤ N, Q ≤ 2000
子任务 #2(54 分):1N,Q7×1041 ≤ N, Q ≤ 7\times 10^4
子任务 #3(18 分): 1N,Q5×1051 ≤ N, Q ≤ 5\times 10^5

感谢 Planet6174 提供的翻译