#include "bits/stdc++.h"
#include "dna.h"
using namespace std;
const int N = 100000;
// const int N = 6;
// cnt_string_letter
vector<int> cnt_a_a(N+1), cnt_a_t(N+1), cnt_a_c(N+1);
vector<int> cnt_b_a(N+1), cnt_b_t(N+1), cnt_b_c(N+1);
vector<int> ov_a(N+1), ov_t(N+1), ov_c(N+1);
void init(string a, string b) {
cnt_a_a[0]=0;
cnt_a_t[0]=0;
cnt_a_c[0]=0;
cnt_b_a[0]=0;
cnt_b_t[0]=0;
cnt_b_c[0]=0;
ov_a[0]=0;
ov_t[0]=0;
ov_c[0]=0;
for (int i=1; i<=(int)a.length(); i++) {
// count prefix sums
cnt_a_a[i] = cnt_a_a[i-1] + (a[i-1]=='A');
cnt_b_a[i] = cnt_b_a[i-1] + (b[i-1]=='A');
cnt_a_t[i] = cnt_a_t[i-1] + (a[i-1]=='T');
cnt_b_t[i] = cnt_b_t[i-1] + (b[i-1]=='T');
cnt_a_c[i] = cnt_a_c[i-1] + (a[i-1]=='C');
cnt_b_c[i] = cnt_b_c[i-1] + (b[i-1]=='C');
// overlap prefix sums
ov_a[i] = ov_a[i-1] + (a[i-1]=='A' && (a[i-1] != b[i-1]));
ov_t[i] = ov_t[i-1] + (a[i-1]=='T' && (a[i-1] != b[i-1]));
ov_c[i] = ov_c[i-1] + (a[i-1]=='C' && (a[i-1] != b[i-1]));
}
// cout << "init:" << endl;
// print_bitset(bita);
// print_bitset(bitb);
// cout << endl;
}
int get_distance(int x, int y) {
cerr << endl;
cerr << "get_distance(" << x << ", " << y << ")" << endl;
// check if counts align
int a_a_cnt = (cnt_a_a[y+1] - cnt_a_a[x]);
int b_a_cnt = (cnt_b_a[y+1] - cnt_b_a[x]);
int a_t_cnt = (cnt_a_t[y+1] - cnt_a_t[x]);
int b_t_cnt = (cnt_b_t[y+1] - cnt_b_t[x]);
int a_c_cnt = (cnt_a_c[y+1] - cnt_a_c[x]);
int b_c_cnt = (cnt_b_c[y+1] - cnt_b_c[x]);
bool a_cnt_match = a_a_cnt == b_a_cnt;
bool t_cnt_match = a_t_cnt == b_t_cnt;
bool c_cnt_match = a_c_cnt == b_c_cnt;
cerr << "A count" << endl;
cerr << a_a_cnt << " " << b_a_cnt << endl;
cerr << "T count" << endl;
cerr << a_t_cnt << " " << b_t_cnt << endl;
cerr << "C count" << endl;
cerr << a_c_cnt << " " << b_c_cnt << endl;
if (!a_cnt_match || !t_cnt_match || !c_cnt_match) {
return -1;
}
// calculate the distance
int ov_cnt_a = ov_a[y+1] - ov_a[x];
int ov_cnt_t = ov_t[y+1] - ov_t[x];
int ov_cnt_c = ov_c[y+1] - ov_c[x];
// one of the characters don't need to be changed
if (ov_cnt_a == 0 || ov_cnt_t == 0 || ov_cnt_c == 0) {
cerr << "one of characters" << endl;
int sm = ov_cnt_a + ov_cnt_t + ov_cnt_c;
return (sm+(sm-1))/2;
}
cerr << "algorithm" << endl;
vector<int> sums = {ov_cnt_a, ov_cnt_t, ov_cnt_c};
return sums[0] + sums[1];
}
// int main() {
// // init("AAABBB", "BBBAAA");
// init("ATACAT", "ACTATA");
// cerr << get_distance(1, 3) << endl;
// cerr << get_distance(4, 5) << endl;
// cerr << get_distance(3, 5) << endl;
// return 0;
// }
