#include "dna.h"
#include "bits/stdc++.h"
using namespace std;
typedef vector<int> vi;
#define sz(x) (int)(x).size()
vector<int> str[2];
int N;
struct node
{
int data[3][3];
node()
{
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
data[i][j] = 0;
}
};
node operator+(const node &a, const node &b)
{
node ret;
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
ret.data[i][j] = a.data[i][j] + b.data[i][j];
return ret;
}
const node EMPTY;
struct segtree
{
int size;
vector<node> arr;
void init()
{
size = 1;
while (size < N)
size *= 2;
arr.resize(2 * size);
for (int i = 0; i < N; ++i)
++arr[size + i].data[str[0][i]][str[1][i]];
for (int i = size - 1; i > 0; --i)
arr[i] = arr[2 * i] + arr[2 * i + 1];
}
node query(int l, int r)
{
return query(l, r, 1, 0, size);
}
node query(int l, int r, int x, int lx, int rx)
{
if (l <= lx && rx <= r)
return arr[x];
if (r <= lx || rx <= l)
return EMPTY;
int m = (lx + rx) / 2;
return query(l, r, 2 * x, lx, m) + query(l, r, 2 * x + 1, m, rx);
}
};
segtree seg;
void init(std::string a, std::string b)
{
N = sz(a);
str[0].resize(N), str[1].resize(N);
vi trans(128, -1);
trans['A'] = 0;
trans['C'] = 1;
trans['T'] = 2;
for (int i = 0; i < N; ++i)
str[0][i] = trans[a[i]], str[1][i] = trans[b[i]];
seg.init();
}
int get_distance(int x, int y)
{
node tmp = seg.query(x, y + 1);
int moves = 0;
for (int i = 0; i < 3; ++i)
tmp.data[i][i] = 0;
int cnt[3] = {0, 0, 0};
for (int i = 0; i < 3; ++i)
for (int j = 0; j < 3; ++j)
cnt[i] += tmp.data[i][j], cnt[j] -= tmp.data[i][j];
for (int i = 0; i < 3; ++i)
if (cnt[i] != 0)
return -1;
int v = 0;
for (int i = 0; i < 3; ++i)
for (int j = i + 1; j < 3; ++j)
{
int mini = min(tmp.data[i][j], tmp.data[j][i]);
moves += mini;
tmp.data[i][j] -= mini;
tmp.data[j][i] -= mini;
v = max(v, max(tmp.data[i][j], tmp.data[j][i]));
}
moves += 2 * v;
return moves;
}
