1694B.md (2060B)
1 Source: https://codeforces.com/problemset/problem/1694/B 2 3 B. Paranoid String 4 5 time limit per test 6 7 1 second 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 Let's call a binary string $T$ of length $m$ indexed from $1$ to $m$ paranoid if we can obtain a string of length $1$ by performing the following two kinds of operations $m-1$ times in any order : 22 23 * Select any substring of $T$ that is equal to 01, and then replace it with 1. 24 * Select any substring of $T$ that is equal to 10, and then replace it with 0. 25 26 For example, if $T = $ 001, we can select the substring $[T_2T_3]$ and perform the first operation. So we obtain $T = $ 01. 27 28 You are given a binary string $S$ of length $n$ indexed from $1$ to $n$. Find the number of pairs of integers $(l, r)$ $1 \le l \le r \le n$ such that $S[l \ldots r]$ (the substring of $S$ from $l$ to $r$) is a paranoid string. 29 30 Input 31 32 The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. The description of test cases follows. 33 34 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the size of $S$. 35 36 The second line of each test case contains a binary string $S$ of $n$ characters $S_1S_2 \ldots S_n$. ($S_i = $ 0 or $S_i = $ 1 for each $1 \le i \le n$) 37 38 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. 39 40 Output 41 42 For each test case, output the number of pairs of integers $(l, r)$ $1 \le l \le r \le n$ such that $S[l \ldots r]$ (the substring of $S$ from $l$ to $r$) is a paranoid string. 43 44 Example 45 46 Input 47 48 ``` 49 5 50 51 1 52 53 1 54 55 2 56 57 01 58 59 3 60 61 100 62 63 4 64 65 1001 66 67 5 68 69 11111 70 ``` 71 72 Output 73 74 ``` 75 1 76 3 77 4 78 8 79 5 80 ``` 81 82 Note 83 84 In the first sample, $S$ already has length $1$ and doesn't need any operations. 85 86 In the second sample, all substrings of $S$ are paranoid. For the entire string, it's enough to perform the first operation. 87 88 In the third sample, all substrings of $S$ are paranoid except $[S_2S_3]$, because we can't perform any operations on it, and $[S_1S_2S_3]$ (the entire string).