#2331. 程序

程序

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给你一个包含n\red{n}个指令的程序,最开始x\red{x}的值为0\red{0}。接下来,每一个指令都在这两种类型之间:

\red{-:}x\red{x}减一;

+\red{+:}x\red{x}加一。

我们设F(S)\red{F(S)}表示执行当前操作序列过程中出现过的不同的数的数量(包括开始时的0\red{0)}

现在有m\red{m}组询问,每次询问给定一段区间[l,r]\red{[l,r],}你需要回答忽略这段操作序列后,求整个序列的F\red{F}值。

输入格式

第一行输入两个整数n,m\red{n,m,}表示指令的个数和询问的个数。

第二行一个仅包含+\red{+}\red{-}的长度为n\red{n}的字符串,表示指令串。

接下来m\red{m}行,每行两个整数l,r\red{l,r,}表示一组询问。

输出格式

对于每个询问输出一行一个整数,表示忽略这段操作序列后,执行当前操作序列过程中出现过的不同的 数的数量。

样例

输入样例

8 4
-+--+--+
1 8
2 8
2 5
1 1

输出样例

1
2
4
4

提示

对于50%\red{50\%}的数据,1<=n,m<=103\red{1<=n,m<=10^3}

对于100%\red{100\%}的数据,a<=n,m<=2×105,1<=l<=r<=n\red{a<=n,m<=2\times 10^5,1<=l<=r<=n}

国庆集训11

未参加
状态
已结束
规则
IOI
题目
7
开始于
2022-10-6 9:00
结束于
2022-10-6 12:00
持续时间
3 小时
主持人
参赛人数
12