F 奇怪的程序(Hard) /[模板]莫队算法

F 奇怪的程序(Hard) /[模板]莫队算法

测试数据来自 nnu_contest/1236

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。一共有两个不同的值。

信息

ID
2876
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者