1849C.md (2398B)
1 Source: https://codeforces.com/problemset/problem/1849/C 2 3 C. Binary String Copying 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 string $s$ consisting of $n$ characters 0 and/or 1. 22 23 You make $m$ copies of this string, let the $i$-th copy be the string $t_i$. Then you perform exactly one operation on each of the copies: for the $i$-th copy, you sort its substring $[l_i; r_i]$ (the substring from the $l_i$-th character to the $r_i$-th character, both endpoints inclusive). Note that each operation affects only one copy, and each copy is affected by only one operation. 24 25 Your task is to calculate the number of different strings among $t_1, t_2, \ldots, t_m$. Note that the initial string $s$ should be counted only if at least one of the copies stays the same after the operation. 26 27 Input 28 29 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 30 31 The first line of each test case contains two integers $n$ and $m$ ($1 \le n, m \le 2 \cdot 10^5$) — the length of $s$ and the number of copies, respectively. 32 33 The second line contains $n$ characters 0 and/or 1 — the string $s$. 34 35 Then $m$ lines follow. The $i$-th of them contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$) — the description of the operation applied to the $i$-th copy. 36 37 The sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. The sum of $m$ over all test cases doesn't exceed $2 \cdot 10^5$. 38 39 Output 40 41 Print one integer — the number of different strings among $t_1, t_2, \ldots, t_m$. 42 43 Example 44 45 Input 46 47 ``` 48 3 49 50 6 5 51 52 101100 53 54 1 2 55 56 1 3 57 58 2 4 59 60 5 5 61 62 1 6 63 64 6 4 65 66 100111 67 68 2 2 69 70 1 4 71 72 1 3 73 74 1 2 75 76 1 1 77 78 0 79 80 1 1 81 ``` 82 83 Output 84 85 ``` 86 3 87 3 88 1 89 ``` 90 91 Note 92 93 Consider the first example. Copies below are given in order of the input operations. Underlined substrings are substrings that are sorted: 94 95 1. 101100 $\rightarrow$ 011100; 96 2. 101100 $\rightarrow$ 011100; 97 3. 101100 $\rightarrow$ 101100; 98 4. 101100 $\rightarrow$ 101100; 99 5. 101100 $\rightarrow$ 000111. 100 101 There are three different strings among $t_1, t_2, t_3, t_4, t_5$: 000111, 011100 and 101100. 102 103 Consider the second example: 104 105 1. 100111 $\rightarrow$ 100111; 106 2. 100111 $\rightarrow$ 001111; 107 3. 100111 $\rightarrow$ 001111; 108 4. 100111 $\rightarrow$ 010111. 109 110 There are three different strings among $t_1, t_2, t_3, t_4$: 001111, 010111 and 100111.