#include "dna.h"
#include <map>
#include <vector>
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
map<char, ll> charmap = {{'A',0},{'C', 1},{'T', 2}};
struct segtree{
struct node{
vector<ll> a;
ll icnt;
};
#define neutral {{0, 0, 0, 0}, 0}
vector<node> t;
ll sz, rsz;
node merge(node l, node r){
node nw; nw.icnt=l.icnt+r.icnt;
nw.a.resize(4);
for (ll i=0; i<4; i++){
nw.a[i]=l.a[i]+r.a[i];
}
return nw;
}
void init(ll N){
sz=N*4;
rsz=N;
t.resize(N);
}
void build(ll tl, ll tr, ll v, string &a, string &b){
if (tl==tr){
t[v] = {{0, 0, 0, 0}, (a[tl]!=b[tl])};
t[v].a[charmap[a[tl]]]++;
t[v].a[charmap[b[tl]]]--;
}else{
ll tm = (tl+tr)/2;
build(tl, tm, v*2, a, b);
build(tm+1, tr, v*2+1, a, b);
t[v]=merge(t[v*2], t[v*2+1]);
}
}
node query(ll l, ll r, ll tl, ll tr, ll v){
if (l==tl and r==tr){
return t[v];
}else if (l>r) return neutral;
else{
ll tm = (tl+tr)/2;
return merge(query(l, min(r, tm), tl, tm, v*2), query(max(l, tm+1), r, tm+1, tr, v*2+1));
}
}
void build(string &a, string &b){
build(0, rsz-1, 1, a, b);
}
ll query(ll l, ll r){
return query(l, r, 0, rsz-1, 1).icnt;
}
};
segtree tr;
void init(std::string a, std::string b) {
tr.init(a.length());
tr.build(a, b);
}
int get_distance(int x, int y) {
int ans = (int)tr.query(x, y);
return ans/2+ans%2;
}
