1473D.md (2178B)
1 Source: https://codeforces.com/problemset/problem/1473/D 2 3 D. Program 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a program that consists of $n$ instructions. Initially a single variable $x$ is assigned to $0$. Afterwards, the instructions are of two types: 22 23 * increase $x$ by $1$; 24 * decrease $x$ by $1$. 25 26 You are given $m$ queries of the following format: 27 28 * query $l$ $r$ — how many distinct values is $x$ assigned to if all the instructions between the $l$-th one and the $r$-th one inclusive are ignored and the rest are executed without changing the order? 29 30 Input 31 32 The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of testcases. 33 34 Then the description of $t$ testcases follows. 35 36 The first line of each testcase contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the number of instructions in the program and the number of queries. 37 38 The second line of each testcase contains a program — a string of $n$ characters: each character is either '+' or '-' — increment and decrement instruction, respectively. 39 40 Each of the next $m$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$) — the description of the query. 41 42 The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$. The sum of $m$ over all testcases doesn't exceed $2 \cdot 10^5$. 43 44 Output 45 46 For each testcase print $m$ integers — for each query $l$, $r$ print the number of distinct values variable $x$ is assigned to if all the instructions between the $l$-th one and the $r$-th one inclusive are ignored and the rest are executed without changing the order. 47 48 Example 49 50 Input 51 52 ``` 53 2 54 8 4 55 -+--+--+ 56 1 8 57 2 8 58 2 5 59 1 1 60 4 10 61 +-++ 62 1 1 63 1 2 64 2 2 65 1 3 66 2 3 67 3 3 68 1 4 69 2 4 70 3 4 71 4 4 72 ``` 73 74 Output 75 76 ``` 77 1 78 2 79 4 80 4 81 3 82 3 83 4 84 2 85 3 86 2 87 1 88 2 89 2 90 2 91 ``` 92 93 Note 94 95 The instructions that remain for each query of the first testcase are: 96 97 1. empty program — $x$ was only equal to $0$; 98 2. "-" — $x$ had values $0$ and $-1$; 99 3. "---+" — $x$ had values $0$, $-1$, $-2$, $-3$, $-2$ — there are $4$ distinct values among them; 100 4. "+--+--+" — the distinct values are $1$, $0$, $-1$, $-2$.