#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
struct node{
int numAT,numAC,numTC,cnt;
};
node f(node x,node y){
node z;
z=x;
z.numAT+=y.numAT;
z.numAC+=y.numAC;
z.numTC+=y.numTC;
z.cnt+=y.cnt;
int num1,num2,num3;
if(x.numAT>=0){
num1=max(z.numAT,0);
}
else{
num1=min(z.numAT,0);
}
if(x.numAC>=0){
num2=max(z.numAC,0);
}
else{
num2=min(z.numAC,0);
}
if(x.numTC>=0){
num3=max(z.numTC,0);
}
else{
num3=min(z.numTC,0);
}
if(abs(x.numAT)>abs(num1)){
z.cnt+=abs(num1-x.numAT);
}
if(abs(x.numAC)>abs(num2)){
z.cnt+=abs(num2-x.numAC);
}
if(abs(x.numTC)>abs(num3)){
z.cnt+=abs(num3-x.numTC);
}
return z;
}
struct segtree{
int size;
vector<node> tree;
void init(int n){
size=1;
while(size<n){
size*=2;
}
node nd;
nd.numAC=0;
nd.numAT=0;
nd.numTC=0;
nd.cnt=0;
tree.assign(2*size,nd);
}
void build(string &a,string &b,int x,int lx,int rx){
if(rx-lx==1){
if(a[lx]!=b[lx]){
if(a[lx]=='A' && b[lx]=='T'){
tree[x].numAT=1;
}
else if(a[lx]=='T' && b[lx]=='A'){
tree[x].numAT=-1;
}
else if(a[lx]=='A' && b[lx]=='C'){
tree[x].numAC=1;
}
else if(a[lx]=='C' && b[lx]=='A'){
tree[x].numAC=-1;
}
else if(a[lx]=='T' && b[lx]=='C'){
tree[x].numTC=1;
}
else{
tree[x].numTC=-1;
}
}
return;
}
int m=(lx+rx)/2;
build(a,b,2*x+1,lx,m);
build(a,b,2*x+2,m,rx);
tree[x]=f(tree[2*x+1],tree[2*x+2]);
}
void build(string &a,string &b){
build(a,b,0,0,size);
}
node get_res(int l,int r,int x,int lx,int rx){
if(lx>=r || rx<=l){
node nd;
nd.numAC=0;
nd.numAT=0;
nd.numTC=0;
nd.cnt=0;
return nd;
}
if(lx>=l && rx<=r){
return tree[x];
}
node s1,s2;
int m=(lx+rx)/2;
s1=get_res(l,r,2*x+1,lx,m);
s2=get_res(l,r,2*x+2,m,rx);
return f(s1,s2);
}
node get_res(int l,int r){
return get_res(l,r+1,0,0,size);
}
};
segtree st;
void init(std::string a, std::string b) {
int n=a.size();
st.init(n);
st.build(a,b);
}
int get_distance(int x, int y) {
node nd=st.get_res(x,y);
int num1,num2,num3;
num1=num2=num3=0;
num1+=nd.numAC;
num2-=nd.numAC;
num1+=nd.numAT;
num3-=nd.numAT;
num3+=nd.numTC;
num2-=nd.numTC;
if(num1!=0 || num2!=0 || num3!=0){
return -1;
}
else{
return nd.cnt+abs(nd.numAC)*2;
}
return 0;
}
