1996C.md (2041B)
1 Source: https://codeforces.com/problemset/problem/1996/C 2 3 C. Sort 4 5 time limit per test 6 7 5 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 two strings $a$ and $b$ of length $n$. Then, you are (forced against your will) to answer $q$ queries. 22 23 For each query, you are given a range bounded by $l$ and $r$. In one operation, you can choose an integer $i$ ($l \leq i \leq r$) and set $a_i = x$ where $x$ is any character you desire. Output the minimum number of operations you must perform such that $\texttt{sorted(a[l..r])} = \texttt{sorted(b[l..r])}$. The operations you perform on one query does not affect other queries. 24 25 For an arbitrary string $c$, $\texttt{sorted(c[l..r])}$ denotes the substring consisting of characters $c_l, c_{l+1}, ... , c_r$ sorted in lexicographical order. 26 27 Input 28 29 The first line contains $t$ ($1 \leq t \leq 1000$) – the number of test cases. 30 31 The first line of each test case contains two integers $n$ and $q$ ($1 \leq n, q \leq 2 \cdot 10^5$) – the length of both strings and the number of queries. 32 33 The following line contains $a$ of length $n$. It is guaranteed $a$ only contains lowercase latin letters. 34 35 The following line contains $b$ of length $n$. It is guaranteed $b$ only contains lowercase latin letters. 36 37 The following $q$ lines contain two integers $l$ and $r$ ($1 \leq l \leq r \leq n$) – the range of the query. 38 39 It is guaranteed the sum of $n$ and $q$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each query, output an integer, the minimum number of operations you need to perform in a new line. 44 45 Example 46 47 Input 48 49 ``` 50 3 51 52 5 3 53 54 abcde 55 56 edcba 57 58 1 5 59 60 1 4 61 62 3 3 63 64 4 2 65 66 zzde 67 68 azbe 69 70 1 3 71 72 1 4 73 74 6 3 75 76 uwuwuw 77 78 wuwuwu 79 80 2 4 81 82 1 3 83 84 1 6 85 ``` 86 87 Output 88 89 ``` 90 0 91 1 92 0 93 2 94 2 95 1 96 1 97 0 98 ``` 99 100 Note 101 102 For the first query, $\texttt{sorted(a[1..5])} =$ abcde and $\texttt{sorted(b[1..5])} =$ abcde, so no operations are necessary. 103 104 For the second query, you need to set $a_1 = $ e. Then, $\texttt{sorted(a[1..4])} = \texttt{sorted(b[1..4])} = $ bcde.