main.cpp (2250B)
1 #include <vector> 2 #include <iostream> 3 #include <unordered_map> 4 5 using namespace std; 6 7 int main() { 8 9 int l, r, n, q, testCases = 0; 10 cin >> testCases; 11 12 for(int z = 0; z < testCases; ++z) { 13 14 cin >> n; 15 cin >> q; 16 17 string a,b = ""; 18 19 cin >> a; 20 cin >> b; 21 22 // create prefix sum arrays per character 23 // then use these to solve problems in O(1) time instead of O(r-l) time 24 25 unordered_map<int, vector<int>> sumsA {}; 26 unordered_map<int, vector<int>> sumsB {}; 27 for(int ch = 0; ch < 26; ++ch) { 28 sumsA[ch] = {}; 29 sumsB[ch] = {}; 30 } 31 32 for(int i = 0; i < a.size(); ++i) { 33 for(int ch = 0; ch < 26; ++ch) { 34 auto& currentCS = sumsA[ch]; 35 if(i != 0) { 36 currentCS.push_back(currentCS[currentCS.size() - 1]); 37 } else { 38 currentCS.push_back(0); 39 } 40 } 41 auto ch = a[i] - 'a'; 42 sumsA[ch][sumsA[ch].size() -1] += 1; 43 } 44 45 for(int i = 0; i < a.size(); ++i) { 46 for(int ch = 0; ch < 26; ++ch) { 47 auto& currentCS = sumsB[ch]; 48 if(i != 0) { 49 currentCS.push_back(currentCS[currentCS.size() - 1]); 50 } else { 51 currentCS.push_back(0); 52 } 53 } 54 auto ch = b[i] - 'a'; 55 sumsB[ch][sumsB[ch].size() -1] += 1; 56 } 57 58 for(int qn = 0; qn < q; ++qn) { 59 cin >> l; 60 cin >> r; 61 62 l -= 1; 63 r -= 1; 64 65 int intersection = 0; 66 67 for(int ch = 0; ch < 26; ++ch) { 68 69 int av = 0; 70 int bv = 0; 71 72 if(l != 0) { 73 av = sumsA[ch][r] - sumsA[ch][l-1]; 74 } else { 75 av = sumsA[ch][r] - 0; 76 } 77 78 if(l != 0) { 79 bv = sumsB[ch][r] - sumsB[ch][l-1]; 80 } else { 81 bv = sumsB[ch][r] - 0; 82 } 83 84 intersection += std::min(av,bv); 85 } 86 87 cout << ((r-l) + 1) - intersection << endl; 88 } 89 } 90 }