#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct {
int seg[4 * N];
void update(int l, int r, int i, int idx, int val){
if (l == r) return seg[i] = val, void();
int mid = (l + r) / 2;
if (idx <= mid) update(l, mid, 2 * i, idx, val);
else update(mid + 1, r, 2 * i + 1, idx, val);
seg[i] = seg[2 * i] + seg[2 * i + 1];
}
int query(int l, int r, int i, int ll, int rr){
if (l >= ll && r <= rr) return seg[i];
if (r < ll || l > rr) return 0;
int mid = (l + r) / 2;
return query(l, mid, 2 * i, ll, rr) + query(mid + 1, r, 2 * i + 1, ll, rr);
}
} segat, segta, segct, segtc, segac, segca, sega, segt, segc;
int n;
void init(std::string a, std::string b) {
n = a.length();
for (int i = 0; i < n; i++) {
if (a[i] == 'A' && b[i] == 'T') segat.update(1, n, 1, i + 1, 1);
if (a[i] == 'T' && b[i] == 'A') segta.update(1, n, 1, i + 1, 1);
if (a[i] == 'A' && b[i] == 'C') segac.update(1, n, 1, i + 1, 1);
if (a[i] == 'C' && b[i] == 'A') segca.update(1, n, 1, i + 1, 1);
if (a[i] == 'T' && b[i] == 'C') segtc.update(1, n, 1, i + 1, 1);
if (a[i] == 'C' && b[i] == 'T') segct.update(1, n, 1, i + 1, 1);
if (a[i] == 'A') sega.update(1, n, 1, i + 1, 1);
if (a[i] == 'T') segt.update(1, n, 1, i + 1, 1);
if (a[i] == 'C') segc.update(1, n, 1, i + 1, 1);
if (b[i] == 'A') sega.update(1, n, 1, i + 1, -1);
if (b[i] == 'T') segt.update(1, n, 1, i + 1, -1);
if (b[i] == 'C') segc.update(1, n, 1, i + 1, -1);
}
}
int get_distance(int x, int y) {
x++, y++;
if (sega.query(1, n, 1, x, y) || segt.query(1, n, 1, x, y) || segc.query(1, n, 1, x, y) ) return -1;
int cnt = 0;
cnt += min(segat.query(1, n, 1, x, y), segta.query(1, n, 1, x, y));
cnt += min(segct.query(1, n, 1, x, y), segtc.query(1, n, 1, x, y));
cnt += min(segac.query(1, n, 1, x, y), segca.query(1, n, 1, x, y));
int left = 0;
left += abs(segat.query(1, n, 1, x, y) - segta.query(1, n, 1, x, y));
left += abs(segct.query(1, n, 1, x, y) - segtc.query(1, n, 1, x, y));
left += abs(segac.query(1, n, 1, x, y) - segca.query(1, n, 1, x, y));
return cnt + left/3*2;
}
/*
for two letters it's trivial that ans = wrong_pos/2
what about three?
observe that wrong positions of A, T, C are in these patterns:
A : they might be in T or C
T : they might be in A or C
C : they might be in A or T
so that means.. wrong_pos[A] + wrong_pos[T] will equal wrong_pos[C] + positions that were swapped between A and T
so ans is wrong_pos[any] + (wrong_pos[smth] + wrong_pos[smth] - wrong_pos[any]) / 2
we can just use A,T,C
cnt[C] + (cnt[A] + cnt[T] - cnt[C]) / 2
shit.. bug.
oh.
there exists a cycle of 3 letters : "ATC", "TCA"
how can we capture all of those...
oh. just create seg of all pairs, at, ta, ct, tc, ac, ca
*/
