F 奇怪的程序(Hard) /[模板]莫队算法
F.奇怪的程序(Hard)
时间限制:2~5秒
(不卡常数)
空间限制:512MB
题目背景
本题的Hard版本与Medium版本唯一的区别在于:本版本中可能出现第三种字符*。
你得到了一份奇怪的代码。
根据说明文档,这份代码只由三种字符构成。程序开始时将自动定义一个初值为0的整型变量X。三个字符和相对应的作用是:
'+',将X增加1。
'-',将X减少1。
'*', 将X增加3。
题目描述
现有m个询问,每个询问给出两个正整数\(l\le r\)
问:仅保留程序的第[l,r]个字符,程序在运行过程中,变量X会取到多少种不同的取值?
初始化的赋值不计算在内
输入格式
第一行包括两个整数\(n,m\),分别表示程序的长度和询问的个数。
第二行包括一个长度为\(n\)的字符串,字符串中仅包含提到的三种字符。
之后的\(m\)行每行包含两个正整数\(1\le l\le r\le n\)
输出格式
共\(m\)行,每行一个整数表示答案。
数据范围及限制
\(n,m\le 10^6\)
样例输入
3 3
-**
1 2
1 3
2 3
样例输出
2
3
2
样例解释
对于第一次询问,x的值分别为:-1,2。一共有两个不同的值。
对于第二次询问,x的值分别为:-1,2,5。一共有三个不同的值。
对于最后一次询问,x的值分别为:3,6。一共有两个不同的值。