#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> MN;
vector<int> MX;
vector<int> V;
string A, B;
vector<bool> visited;
bool subtask1 = true;
void build(int p, int L, int R){
if(L == R){
MN[p] = L;
MX[p] = L;
return;
}
int mid = (L+R)/2;
build(p*2, L, mid);
build(p*2+1, mid+1, R);
int idx1 = MN[p*2];
int idx2 = MN[p*2+1];
if(V[idx1] <= V[idx2]) MN[p] = idx1;
else MN[p] = idx2;
idx1 = MX[p*2];
idx2 = MX[p*2+1];
if(V[idx1] >= V[idx2]) MX[p] = idx1;
else MX[p] = idx2;
}
int get(int p, int L, int R, int i, int j, int v){
if(i > R || j < L) return -1;
if(i <= L && R <= j){
if((v == -1 && V[MN[p]] != -1) || (v == 1 && V[MX[p]] != 1)) return -1;
int low = L;
int high = R;
// int ret = -1;
while(low < high){
int mid = low +(high-low)/2;
if((v == -1 && V[MN[p*2]] == -1) || (v == 1 && V[MX[p*2]] == 1) ){
// ret = mid;
high = mid;
p*=2;
}else low = mid+1, p = 2*p+1;
}
return low;
}
int mid = (L+R)/2;
int ret1 = get(p*2, L, mid, i, j, v);
if(ret1 != -1) return ret1;
return get(p*2+1, mid+1, R, i, j, v);
}
void update(int p, int L, int R, int i, int v){
if(i > R || i < L) return;
if(i == R && L == i){
MX[p] = L;
MN[p] = L;
V[i] = v;
return;
}
int mid = (L+R)/2;
update(p*2, L, mid, i, v);
update(p*2+1, mid+1, R, i, v);
int idx1 = MN[p*2];
int idx2 = MN[p*2+1];
if(V[idx1] <= V[idx2]) MN[p] = idx1;
else MN[p] = idx2;
idx1 = MX[p*2];
idx2 = MX[p*2+1];
if(V[idx1] >= V[idx2]) MX[p] = idx1;
else MX[p] = idx2;
}
void init(std::string a, std::string b) {
N = a.length();
V.assign(N, 0);
visited.assign(N, false);
MN.assign(N*4+1, 0);
MX.assign(N*4+1, 0);
A = a;
B = b;
for(int i = 0; i < N; i++){
if(a[i] == 'T' && b[i] == 'A') V[i] = 1;
if(a[i] == 'A' && b[i] == 'T') V[i] = -1;
if(a[i] == b[i]) V[i] = 0;
}
// ATTATATA TATTATTA
build(1, 0, N-1);
}
int get_distance(int x, int y) {
if(y-x <= 2){
// questo codice va bene se ci sono solo due valori presenti tra i due
int cntA = 0, cntA1 = 0;
int cntT = 0, cntT1 = 0;
int cntC = 0, cntC1 = 0;
for(int i = x; i <= y; i++){
cntA += A[i] == 'A';
cntT += A[i] == 'T';
cntC += A[i] == 'C';
cntA1 += B[i] == 'A';
cntT1 += B[i] == 'T';
cntC1 += B[i] == 'C';
}
if(cntA != cntA1 || cntT != cntT1 || cntC != cntC1) return -1;
if(cntA == 1 && cntT == 1 && cntC == 1){
int cnt = 0;
for(int i = x; i <= y; i++){
if(A[i] == B[i]) cnt++;
}
if(cnt == 3) return 0;
if(cnt == 1) return 1;
return 2;
}
map<int, bool> mp;
int cnt = 0;
for(int i = x; i <= y; i++){
if((A[i] == B[i]) || mp[i]) continue;
if(i == y)
return -1;
bool ok = false;
for(int j = i+1; j <= y; j++){
if(A[i] == B[j] && B[i] == A[j] && !mp[j]){
cnt++;
ok = mp[j] = true;
break;
}
}
if(!ok) return -1;
}
return cnt;
}
int cnt = 0;
bool ok = true;
vector<int> save;
for(int i = x; i <= y; i++){
save.push_back(V[i]);
}
for(int i = x; i <= y; i++){
int idx = -1;
if(i == y && V[i] != 0){
ok = false;
break;
}
if(V[i] == 1)
idx = get(1, 0, N-1, i+1, y, -1);
else if(V[i] == -1)
idx = get(1, 0, N-1, i+1, y, 1);
else continue;
if(idx == -1) {
ok = false;
break;
}
cnt++;
update(1, 0, N-1, idx, 0);
}
for(int i = x; i <= y; i++){
update(1, 0, N-1, i, save[i-x]);
}
if(!ok) return -1;
return cnt;
}
