#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using paira = array<int, 2>;
int n = 1;
vector<int> same(1);
vector<vector<int>> counta(3, vector<int>(1));
auto countb = counta;
void init(string a, string b) {
n = a.size();
same.resize(n+1);
for (int i = 0; i < 3; i++) {
counta[i].resize(n+1);
countb[i].resize(n+1);
}
for (int i = 0; i < n; i++) {
int ai = (a[i] == 'A' ? 0 : (a[i] == 'C' ? 1 : 2));
int bi = (b[i] == 'A' ? 0 : (b[i] == 'C' ? 1 : 2));
counta[ai][i+1]= (i == 0 ? 1 : counta[(ai)%3][i] + 1);
counta[(ai + 1)%3][i+1] = (i == 0 ? 0 : counta[(ai + 1)%3][i]);
counta[(ai + 2) %3][i+1] = (i == 0 ? 0 : counta[(ai + 2)%3][i]);
countb[bi][i+1]= (i == 0 ? 1 : countb[(bi)%3][i] + 1);
countb[(bi + 1)%3][i+1] = (i == 0 ? 0 : countb[(bi + 1)%3][i]);
countb[(bi + 2) %3][i+1] = (i == 0 ? 0 : countb[(bi + 2)%3][i]);
same[i + 1] = (i == 0 ? 0 : same[i]) + (ai == bi);
}
}
int get_distance(int x, int y) {
for (int i = 0; i < 3 ; i++) {
if (counta[i][y+1] - counta[i][x] != countb[i][y+1] - countb[i][x]) {
return -1;
}
}
ll ans = 0;
for (int i = 0; i < 3; i++) {
ans += counta[i][y+1] - counta[i][x];
}
ans -= (same[y+1] - same[x]);
return (ans + 1)/2;
}
/*
constraints n = 1e5
q = 1e5
at most 3 different
q*log(n) or q solution allowed
same[n] = number of "matching" indices for x and y until n
then
If two strings who are derranged permutations of each other then their edit distance is
for even n n/2
for odd n (n-1)/2 + 1 = (n-1+2)/2 = (n+1)/2
*/
