#include <iostream>
#include <vector>
struct Count {
int a1, a2;
int t1, t2;
int c1, c2;
int at, ta;
int ac, ca;
int tc, ct;
Count()
: a1(0),
a2(0),
t1(0),
t2(0),
c1(0),
c2(0),
at(0),
ta(0),
ac(0),
ca(0),
tc(0),
ct(0) {}
Count operator+(const Count &rhs) const {
Count res = *this;
res += rhs;
return res;
}
void operator+=(const Count &rhs) {
a1 += rhs.a1;
a2 += rhs.a2;
t1 += rhs.t1;
t2 += rhs.t2;
c1 += rhs.c1;
c2 += rhs.c2;
at += rhs.at;
ta += rhs.ta;
ac += rhs.ac;
ca += rhs.ca;
tc += rhs.tc;
ct += rhs.ct;
}
};
struct SegmentTree {
std::vector<Count> values;
int offset;
SegmentTree(int n) {
offset = 1;
while (offset < n) offset *= 2;
values = std::vector<Count>(2 * offset);
}
void update(int idx, Count count_diff) {
idx += offset;
while (idx > 0) {
values[idx] += count_diff;
idx /= 2;
}
}
Count query(int l, int r) const {
Count count;
l += offset;
r += offset;
while (l < r) {
if (l & 1) count += values[l++];
if (r & 1) count += values[--r];
l /= 2;
r /= 2;
}
return count;
}
};
std::string a, b;
SegmentTree st(0);
void init(std::string A, std::string B) {
a = A;
b = B;
st = SegmentTree(A.size());
for (int i = 0; i < A.size(); i++) {
Count diff;
if (A[i] == 'A') diff.a1 += 1;
if (B[i] == 'A') diff.a2 += 1;
if (A[i] == 'T') diff.t1 += 1;
if (B[i] == 'T') diff.t2 += 1;
if (A[i] == 'C') diff.c1 += 1;
if (B[i] == 'C') diff.c2 += 1;
if (A[i] == 'A' && B[i] == 'T') diff.at += 1;
if (A[i] == 'T' && B[i] == 'A') diff.ta += 1;
if (A[i] == 'A' && B[i] == 'C') diff.ac += 1;
if (A[i] == 'C' && B[i] == 'A') diff.ca += 1;
if (A[i] == 'T' && B[i] == 'C') diff.tc += 1;
if (A[i] == 'C' && B[i] == 'T') diff.ct += 1;
st.update(i, diff);
}
}
int get_distance(int x, int y) {
y += 1;
Count count = st.query(x, y);
if (count.a1 != count.a2 || count.t1 != count.t2 || count.c1 != count.c2) {
return -1;
}
// std::cout << count.at << ' ' << count.ta << ' ' << count.ac << ' ' << count.ca << ' ' << count.tc << ' ' << count.ct << '\n';
int at_pairs = std::min(count.at, count.ta);
int ac_pairs = std::min(count.ac, count.ca);
int tc_pairs = std::min(count.tc, count.ct);
int total = at_pairs + ac_pairs + tc_pairs;
count.at -= at_pairs;
count.ta -= at_pairs;
count.ac -= ac_pairs;
count.ca -= ac_pairs;
count.tc -= tc_pairs;
count.ct -= tc_pairs;
// std::cout << count.at << ' ' << count.ta << ' ' << count.ac << ' ' << count.ca << ' ' << count.tc << ' ' << count.ct << '\n';
return total + std::max(count.at, count.ta) * 2;
}
