#include "dna.h" #include<bits/stdc++.h> using namespace std; int n, cd[100005][3][3]; void init(string a, string b) { memset(cd, 0, sizeof(cd)); n = a.size(); a = '&' + a; b = '&' + b; for(int i = 1; i <= n; i++){ int x, y; if(a[i] == 'A') x = 0; else if(a[i] == 'C') x = 2; else x = 1; if(b[i] == 'A') y = 0; else if(b[i] == 'C') y = 2; else y = 1; cd[i][x][y] = 1; for(int j = 0; j < 3; j++){ for(int k = 0; k < 3; k++){ cd[i][j][k] += cd[i-1][j][k]; } } } } int get_distance(int l, int r) { int c[3][3]; l++; r++; for(int i = 0; i < 3; i++){ for(int j = 0; j < 3; j++) c[i][j] = cd[r][i][j] - cd[l-1][i][j]; } int ans = 0; int add = min(c[0][1], c[1][0]); ans += add; c[0][1] -= add; c[1][0] -= add; add = min(c[1][2], c[2][1]); ans += add; c[1][2] -= add; c[2][1] -= add; add = min(c[0][2], c[2][0]); ans += add; c[0][2] -= add; c[2][0] -= add; if(c[0][1] != c[1][2] || c[1][2] != c[2][0] || c[1][0] != c[0][2] || c[0][2] != c[2][1]) return -1; ans += (c[0][1] + c[1][0]) * 2; return ans; }