#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100000;
vector<int> paA(MAX + 1), paT(MAX + 1), paC(MAX + 1), pbA(MAX + 1), pbT(MAX + 1), pbC(MAX + 1);
vector<int> pAT(MAX + 1), pTA(MAX + 1), pAC(MAX + 1), pCA(MAX + 1), pTC(MAX + 1), pCT(MAX + 1);
void init(string a, string b)
{
paA[0] = paT[0] = paC[0] = pbA[0] = pbT[0] = pbC[0] = pAT[0] = pTA[0] = pAC[0] = pCA[0] = pTC[0] = pCT[0] = 0;
for (int i = 0; i < a.size(); i++)
{
paA[i + 1] = paA[i] + (a[i] == 'A');
paT[i + 1] = paT[i] + (a[i] == 'T');
paC[i + 1] = paC[i] + (a[i] == 'C');
pbA[i + 1] = pbA[i] + (b[i] == 'A');
pbT[i + 1] = pbT[i] + (b[i] == 'T');
pbC[i + 1] = pbC[i] + (b[i] == 'C');
pAT[i + 1] = pAT[i];
pTA[i + 1] = pTA[i];
pAC[i + 1] = pAC[i];
pCA[i + 1] = pCA[i];
pTC[i + 1] = pTC[i];
pCT[i + 1] = pCT[i];
if (a[i] == 'A' && b[i] == 'T')
pAT[i + 1]++;
else if (a[i] == 'T' && b[i] == 'A')
pTA[i + 1]++;
else if (a[i] == 'A' && b[i] == 'C')
pAC[i + 1]++;
else if (a[i] == 'C' && b[i] == 'A')
pCA[i + 1]++;
else if (a[i] == 'T' && b[i] == 'C')
pTC[i + 1]++;
else if (a[i] == 'C' && b[i] == 'T')
pCT[i + 1]++;
}
}
int get_distance(int x, int y)
{
int caA = paA[y + 1] - paA[x];
int caT = paT[y + 1] - paT[x];
int caC = paC[y + 1] - paC[x];
int cbA = pbA[y + 1] - pbA[x];
int cbT = pbT[y + 1] - pbT[x];
int cbC = pbC[y + 1] - pbC[x];
if (caA != cbA || caT != cbT || caC != cbC)
return -1;
int AT = pAT[y + 1] - pAT[x];
int TA = pTA[y + 1] - pTA[x];
int AC = pAC[y + 1] - pAC[x];
int CA = pCA[y + 1] - pCA[x];
int TC = pTC[y + 1] - pTC[x];
int CT = pCT[y + 1] - pCT[x];
int d = min(AT, TA) + min(AC, CA) + min(TC, CT);
int m = AT + TA + AC + CA + TC + CT;
int r = m - (2 * d);
return d + (2 * (r / 3));
}
