#include "dna.h"
#include<bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;
using ll = long long;
using str = string;
struct Ans {
ll A, T, C;
Ans() : A(0), T(0), C(0) {}
Ans(ll a, ll t, ll c) {
A = a; T = t; C = c;
}
Ans operator+(const Ans &two) const {
return Ans(A+two.A,T+two.T,C+two.C);
}
bool operator!=(const Ans&two) const {
return not(A == two.A and T == two.T and C == two.C);
}
};
struct Segtree {
ll l, r;
Segtree *lt, *rt;
Ans freq;
void combine() {
freq = lt->freq + rt->freq;
}
Segtree() : l(0), r(0), lt(nullptr), rt(nullptr), freq(Ans(0,0,0)) {}
Segtree(ll left, ll right, vec<Ans>&a) {
l = left; r = right;
lt = rt = nullptr;
if(l == r) {
freq = a[l];
return;
}
ll m = (l+r)>>1;
lt = new Segtree(l,m,a);
rt = new Segtree(m+1,r,a);
combine();
}
Ans query(ll ql, ll qr) {
if(qr < l or r < ql) return {0,0,0};
if(ql <= l and r <= qr) return freq;
return lt->query(ql,qr) + rt->query(ql,qr);
}
};
Segtree diffs, Atree, Btree;
void init(str a, str b) {
ll n = a.length();
vec<Ans> countA(n), countB(n);
vec<Ans> mismatch(n);
for(int i = 0; i < n; i++) {
countA[i] = {0,0,0};
countB[i] = {0,0,0};
mismatch[i] = {0,0,0};
mismatch[i].A = (a[i] != b[i]);
if(a[i] == 'A') countA[i].A = 1;
else if(a[i] == 'T') countA[i].T = 1;
else if(a[i] == 'C') countA[i].C = 1;
if(b[i] == 'A') countB[i].A = 1;
else if(b[i] == 'T') countB[i].T = 1;
else if(b[i] == 'C') countB[i].C = 1;
}
cerr << "Count done" << endl;
diffs = Segtree(0,n-1,mismatch);
Atree = Segtree(0,n-1,countA);
Btree = Segtree(0,n-1,countB);
cerr << "Segtrees done" << endl;
}
int get_distance(int x, int y) {
Ans aCount = Atree.query(x,y);
Ans bCount = Btree.query(x,y);
if(aCount != bCount) {
return -1;
}
ll ans = diffs.query(x,y).A;
return (ans+1)/2;
}
