codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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.