#include<bits/stdc++.h>
#include "dna.h"
using namespace std;
struct T{
int alph_A[3] = {0, 0, 0}, alph_B[3] = {0, 0, 0};
int diff = 0;
};
string a, b;
struct SegTree{
vector<T>sTree;
T comb(T a, T b){
T res;
res.diff = a.diff + b.diff;
for(int i = 0;i < 3;++i){
res.alph_A[i] += a.alph_A[i];
res.alph_A[i] += b.alph_A[i];
res.alph_B[i] += a.alph_B[i];
res.alph_B[i] += b.alph_B[i];
}
return res;
}
void Build(int node, int l, int r){
if(l == r){
sTree[node].diff = (a[l] != b[l]);
if(a[l] == 'A')sTree[node].alph_A[0]++;
if(a[l] == 'T')sTree[node].alph_A[1]++;
if(a[l] == 'C')sTree[node].alph_A[2]++;
if(b[l] == 'A')sTree[node].alph_B[0]++;
if(b[l] == 'T')sTree[node].alph_B[1]++;
if(b[l] == 'C')sTree[node].alph_B[2]++;
}
else{
int mid = (l + r) >> 1;
Build(node * 2, l, mid);
Build(node * 2 + 1, mid + 1, r);
sTree[node] = comb(sTree[node * 2], sTree[node * 2 + 1]);
}
}
T Query(int node, int l, int r, int ql, int qr){
T Res;
if(ql <= l && r <= qr)return sTree[node];
if(ql > r || qr < l)return Res;
int mid = (l + r) >> 1;
T Lc = Query(node * 2, l, mid, ql, qr);
T Rc = Query(node * 2 + 1, mid + 1, r, ql, qr);
Res = comb(Lc, Rc);
return Res;
}
};
SegTree st;
void init(string A, string B){
a = " ", b = " ";
a += A, b += B;
st.sTree.resize(4 * A.length());
st.Build(1, 1, A.length());
}
int get_distance(int x, int y){
x++;
y++;
T q = st.Query(1, 1, a.length() - 1, x, y);
for(int i = 0;i < 3;++i){
if(q.alph_A[i] != q.alph_B[i])return -1;
}
return q.diff - 1;
}
//int main(){
// init("ATACAT", "ACTATA");
// cout << get_distance(3, 5);
//}
