← 返回题目列表

Codeforces · 1473/D

D. 程序

中文机器翻译题面 查看原题

给你一个由 $$$n$$$ 指令组成的程序。最初,单个变量 $$$x$$$ 被分配给 $$$0$$$。之后,指令有两种类型:

- 将 $$$x$$$ 增加 $$$1$$$;
- 将 $$$x$$$ 减少 $$$1$$$。

您将收到以下格式的 $$$m$$$ 查询:

- 查询 $$$l$$$ $$$r$$$ — 如果忽略第 $$$l$$$ 和第 $$$r$$$ 之间的所有指令,而执行其余指令而不更改顺序,则 $$$x$$$ 会分配多少个不同的值?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) - 程序中的指令数和查询数。

每个测试用例的第二行包含一个程序 - 一个由 $$$n$$$ 字符组成的字符串:每个字符要么是“+”,要么是“-”——分别是递增和递减指令。

接下来的 $$$m$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) - 查询的描述。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印 $$$m$$$ 整数 - 对于每个查询 $$$l$$$,$$$r$$$ 打印分配给变量 $$$x$$$ 的不同值的数量,前提是忽略第 $$$l$$$ 和第 $$$r$$$ 之间的所有指令,并且执行其余指令而不更改顺序。

示例

输入 #1

2
8 4
-+--+--+
1 8
2 8
2 5
1 1
4 10
+-++
1 1
1 2
2 2
1 3
2 3
3 3
1 4
2 4
3 4
4 4

输出 #1

1
2
4
4
3
3
4
2
3
2
1
2
2
2

注意

第一个测试用例的每个查询保留的指令是:

1. 空程序——$$$x$$$ 只等于$$$0$$$;
2. “-”— $$$x$$$ 的值为 $$$0$$$ 和 $$$-1$$$;
3. "---+" — $$$x$$$ 的值为 $$$0$$$、$$$-1$$$、$$$-2$$$、$$$-3$$$、$$$-2$$$ — 其中有 $$$4$$$ 不同的值;
4.“+--+--+”— 不同的值为 $$$1$$$、$$$0$$$、$$$-1$$$、$$$-2$$$。