#include <bits/stdc++.h>
#include "dna.h"
using namespace std;
struct Info {
int AonT, AonC;
int TonA, TonC;
int ConA, ConT;
// A, T, C;
};
int n;
Info t[401010];
string A, B;
void build(int v, int vl, int vr) {
if (vl == vr) {
if (A[vl] == B[vl])return;
if (A[vl] == 'A' && B[vl] == 'T')t[v].AonT = 1;
if (A[vl] == 'A' && B[vl] == 'C')t[v].AonC = 1;
if (A[vl] == 'T' && B[vl] == 'A')t[v].TonA = 1;
if (A[vl] == 'T' && B[vl] == 'C')t[v].TonC = 1;
if (A[vl] == 'C' && B[vl] == 'A')t[v].ConA = 1;
if (A[vl] == 'C' && B[vl] == 'T')t[v].ConT = 1;
return;
}
int vm = (vl + vr) / 2;
build(2 * v, vl, vm);
build(2 * v + 1, vm + 1, vr);
t[v].AonT = t[2 * v].AonT + t[2 * v + 1].AonT;
t[v].AonC = t[2 * v].AonC + t[2 * v + 1].AonC;
t[v].TonA = t[2 * v].TonA + t[2 * v + 1].TonA;
t[v].TonC = t[2 * v].TonC + t[2 * v + 1].TonC;
t[v].ConA = t[2 * v].ConA + t[2 * v + 1].ConA;
t[v].ConT = t[2 * v].ConT + t[2 * v + 1].ConT;
return;
}
Info gt(int v, int vl, int vr, int l, int r) {
if (l <= vl && vr <= r)return t[v];
if (r < vl || vr < l)return {0, 0, 0, 0, 0, 0};
int vm = (vl + vr) / 2;
auto f = gt(2 * v, vl, vm, l, r);
auto s = gt(2 * v + 1, vm + 1, vr, l, r);
return {f.AonT + s.AonT, f.AonC + s.AonC,
f.TonA + s.TonA, f.TonC + s.TonC,
f.ConA + s.ConA, f.ConT + s.ConT};
}
int acntA[101010], acntT[101010], acntC[101010];
int bcntA[101010], bcntT[101010], bcntC[101010];
void init(std::string a, std::string b) {
n = a.size();
A = a; B = b;
build(1, 0, n - 1);
for (int i = 0; i < n; i++) {
if (i > 0) {
acntA[i] = acntA[i - 1];
acntT[i] = acntT[i - 1];
acntC[i] = acntC[i - 1];
bcntA[i] = bcntA[i - 1];
bcntT[i] = bcntT[i - 1];
bcntC[i] = bcntC[i - 1];
}
if (a[i] == 'A')acntA[i]++;
if (a[i] == 'T')acntT[i]++;
if (a[i] == 'C')acntC[i]++;
if (b[i] == 'A')bcntA[i]++;
if (b[i] == 'T')bcntT[i]++;
if (b[i] == 'C')bcntC[i]++;
}
}
int get_distance(int x, int y) {
int aA = acntA[y], aT = acntT[y], aC = acntC[y];
if (x > 0){aA -= acntA[x - 1]; aT -= acntT[x - 1]; aC -= acntC[x - 1];}
int bA = bcntA[y], bT = bcntT[y], bC = bcntC[y];
if (x > 0){bA -= bcntA[x - 1]; bT -= bcntT[x - 1]; bC -= bcntC[x - 1];}
if (aA != bA || aT != bT || aC != bC)return -1;
auto have = gt(1, 0, n - 1, x, y);
int ans = 0;
{
int M = min(have.AonT, have.TonA);
have.AonT -= M;
have.TonA -= M;
ans += M;
}
{
int M = min(have.AonC, have.ConA);
have.AonC -= M;
have.ConA -= M;
ans += M;
}
{
int M = min(have.TonC, have.ConT);
have.TonC -= M;
have.ConT -= M;
ans += M;
}
int F = max(have.AonT, have.TonA);
int S = max(have.AonC, have.ConA);
int T = max(have.TonC, have.ConT);
ans += (max({F, S, T}) + max({min(F, S), min(S, T), min(F, T)}));
/*
struct Info {
int AonT, AonC;
int TonA, TonC;
int ConA, ConT;
// A, T, C;
};
*/
return ans;
}
/**
6 3
ATACAT
ACTATA
1 3
4 5
3 5
*/
