/* 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 = 1e5 + 5; int n, pre1[3][maxn], pre2[3][maxn]; int p1[maxn]; // A-T int p2[maxn]; // T-A int p3[maxn]; // T-C int p4[maxn]; // C-T int p5[maxn]; // A-C int p6[maxn]; // C-A void init(string a, string b) { n = a.size(); FOR(i,0,n-1) { if (a[i] == 'A' && b[i] == 'T') p1[i] = 1; if (a[i] == 'T' && b[i] == 'A') p2[i] = 1; if (a[i] == 'T' && b[i] == 'C') p3[i] = 1; if (a[i] == 'C' && b[i] == 'T') p4[i] = 1; if (a[i] == 'A' && b[i] == 'C') p5[i] = 1; if (a[i] == 'C' && b[i] == 'A') p6[i] = 1; 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]; p1[i] += p1[i - 1]; p2[i] += p2[i - 1]; p3[i] += p3[i - 1]; p4[i] += p4[i - 1]; p5[i] += p5[i - 1]; p6[i] += p6[i - 1]; } } } int get_distance(int x, int y) { // differ : A-T, C-T, A-C, T-A, T-C, C-A // ACAT // TTCA 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; } int t1, t2, t3, t4, t5, t6; if (x == 0) { t1 = p1[y]; t2 = p2[y]; t3 = p3[y]; t4 = p4[y]; t5 = p5[y]; t6 = p6[y]; } else { t1 = p1[y] - p1[x - 1]; t2 = p2[y] - p2[x - 1]; t3 = p3[y] - p3[x - 1]; t4 = p4[y] - p4[x - 1]; t5 = p5[y] - p5[x - 1]; t6 = p6[y] - p6[x - 1]; } int res = 0; if (t1 < t2) swap(t1, t2); if (t3 < t4) swap(t3, t4); if (t5 < t6) swap(t5, t6); res = t2 + t4 + t6; t1 -= t2; t3 -= t4; t5 -= t6; if (t1 > 0) res += 2; return res; }