#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
int N;
vector<int> MN;
vector<int> MX;
vector<int> V;
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);
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){
map<int, bool> mp;
int cnt = 0;
for(int i = x; i <= y; i++){
if(V[i] == 0 || mp[i]) continue;
if(i == y && !mp[i] && V[i] != 0) return -1;
bool ok = false;
for(int j = i+1; j <= y; j++){
if(V[j] == -V[i] && !mp[j]){
cnt++;
mp[j] = true;
ok = true;
continue;
}
}
if(!ok) return -1;
}
return cnt;
}
vector<int> init = V;
int cnt = 0;
bool ok = true;
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, init[i]);
}
if(!ok) return -1;
return cnt;
}
