problem.txt (2692B)
1 C. Sort 2 time limit per test 3 5 seconds 4 memory limit per test 5 256 megabytes 6 7 You are given two strings a and b of length n. Then, you are (forced against your will) to answer q queries. 8 9 For each query, you are given a range bounded by l and r. In one operation, you can choose an integer i (l≤i≤r) and set ai=x where x is any character you desire. Output the minimum number of operations you must perform such that sorted(a[l..r])=sorted(b[l..r]). The operations you perform on one query does not affect other queries. 10 11 For an arbitrary string c, sorted(c[l..r]) denotes the substring consisting of characters cl,cl+1,...,cr sorted in lexicographical order. 12 Input 13 14 The first line contains t (1≤t≤1000) – the number of test cases. 15 16 The first line of each test case contains two integers n and q (1≤n,q≤2⋅105) – the length of both strings and the number of queries. 17 18 The following line contains a of length n. It is guaranteed a only contains lowercase latin letters. 19 20 The following line contains b of length n. It is guaranteed b only contains lowercase latin letters. 21 22 The following q lines contain two integers l and r (1≤l≤r≤n) – the range of the query. 23 24 It is guaranteed the sum of n and q over all test cases does not exceed 2⋅105. 25 Output 26 27 For each query, output an integer, the minimum number of operations you need to perform in a new line. 28 29 --- 30 31 - strings a and b of length n 32 - answer q queries 33 - given a range bounded by l and r 34 - in one operation you can select one i s.t. l <= i <= r and set a_i = x 35 - where x is any character you desire 36 - output min number of ops you must perform such that: 37 - sorted(a[l...r]) = sorted(b[l...r]) 38 - operations don't persist across queries 39 40 --- 41 42 examples 43 44 45 5 3 46 abcde 47 edcba 48 1 5 49 1 4 50 3 3 51 52 n = 5 53 q = 3 54 55 56 a = abcde 57 b = edcba 58 both of the strings have length of n 59 60 (latin letters only) 61 62 following q lines (q = 3) 63 64 1 5 65 1 4 66 3 3 67 68 l = 1, r = 5 69 l = 1, r = 4 70 l = 3, r = 3 71 72 q1 = 1,5 73 74 a = abcde 75 b = edcba 76 77 sorted(abcde) = abcde 78 sorted(edcba) = abcde 79 80 ops = 0 81 print(0) 82 83 l = 1, r = 4 84 85 sorted(abcd) = abcd 86 sorted(edcb) = bcde 87 88 b->e in first 89 90 we then have: 91 92 sorted(ebcd) = bcde 93 sorted(edcb) = bcde 94 95 we may also do e->a within b to find: 96 97 sorted(abcd) = abcd 98 sorted(adcb) = abcd 99 100 idea: 101 - compute the elements that aren't in both...? 102 - how do we know which one should get the change in this context they're undistinguished... 103 - count the numbers of each character per word then: 104 - for each of the characters in a that aren't in b: 105 - flip them to a character not in a that is in b 106 107 108 l = 3, r = 3 109 110 sorted(c) = c 111 sorted(c) = c 112 113 sum intersection = 1 114 return sum_intersection - size = 0 115 116 ---