/* author : TIT_manh */ #include <iostream> #include <vector> #include <string> #include <algorithm> #include <cmath> #include <iomanip> #include <cstdio> #include <cstdlib> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <stack> #include <deque> #include <bitset> #include <numeric> #include <functional> #include <cassert> #include <sstream> #include <climits> #define ll long long #define FOR(i,l,r) for (int i = l; i <= r; i++) #define FOD(i,r,l) for (int i = r; i >= l; i--) #define fi first #define se second #define pb push_back #define endl "\n" using namespace std; const int maxn = 2e5 + 5; int n, pre1[3][maxn], pre2[3][maxn], p[maxn]; void init(string a, string b) { n = a.size(); FOR(i,0,n-1) { if (i != 0) p[i] = p[i - 1]; if (a[i] != b[i]) { p[i]++; } if (a[i] == 'A') { pre1[0][i] = 1; } if (a[i] == 'C') { pre1[1][i] = 1; } if (a[i] == 'T') { pre1[2][i] = 1; } if (b[i] == 'A') { pre2[0][i] = 1; } if (b[i] == 'C') { pre2[1][i] = 1; } if (b[i] == 'T') { pre2[2][i] = 1; } if (i != 0) { pre1[0][i] += pre1[0][i - 1]; pre1[1][i] += pre1[1][i - 1]; pre1[2][i] += pre1[2][i - 1]; pre2[0][i] += pre2[0][i - 1]; pre2[1][i] += pre2[1][i - 1]; pre2[2][i] += pre2[2][i - 1]; } } } int get_distance(int x, int y) { FOR(i,0,2) { if (x == 0) { if (pre1[i][y] != pre2[i][y]) return -1; } else if (pre1[i][y] - pre1[i][x - 1] != pre2[i][y] - pre2[i][x - 1]) return -1; } if (x == 0) { return (p[y] / 2) + (p[y] % 2); } else return ((p[y] - p[x - 1]) / 2) + ((p[y] - p[x - 1]) % 2); }