#include "dna.h"
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = std::priority_queue<T>;
template<typename T>
using prior = std::priority_queue<T, vector<T>, greater<T>>;
#define X first
#define Y second
#define eb emplace_back
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
namespace {
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1 << 17;
int N, BIT[maxn];
string A, B;
vector<tuple<int, int, int>> cntA, cntB;
int trans[256];
void bit_add(int idx, int val) {
++idx; /// make sure index \ne 0 -> shift BIT right by 1
while (idx < maxn) BIT[idx] += val, idx += idx & -idx;
}
int bit_sum(int idxL, int idxR, int ans = 0) {
++idxR; /// make sure idxL \ne 0 -> shift BIT right by 1
while (idxR) ans += BIT[idxR], idxR -= idxR & -idxR;
while (idxL) ans -= BIT[idxL], idxL -= idxL & -idxL;
return ans;
}
inline int is_same_dna(int L, int R) {
if (L == 0) {
return cntA[R] == cntB[R];
}
auto &[LAA, LAT, LAC] = cntA[L-1];
auto &[LBA, LBT, LBC] = cntB[L-1];
auto &[RAA, RAT, RAC] = cntA[R];
auto &[RBA, RBT, RBC] = cntB[R];
return (RAA - LAA == RBA - LBA) and
(RAT - LAT == RBT - LBT) and
(RAC - LAC == RBC - LBC);
}
} /// end of namespace
void init(string _A, string _B) {
A = _A, B = _B, N = A.size();
cntA.assign(N, {0, 0, 0}), cntB.assign(N, {0, 0, 0});
trans['A'] = 0, trans['T'] = 1, trans['C'] = 2;
for (int i = 0; i < N; ++i) {
if (i) cntA[i] = cntA[i-1], cntB[i] = cntB[i-1];
auto &[AA, AT, AC] = cntA[i];
auto &[BA, BT, BC] = cntB[i];
if (A[i] == 'A') ++AA; if (A[i] == 'T') ++AT; if (A[i] == 'C') ++AC;
if (B[i] == 'A') ++BA; if (B[i] == 'T') ++BT; if (B[i] == 'C') ++BC;
}
}
/*
CAACTATCT
ATTCTCACA
CAACTATCT
ACACTATCT +1
ATCACATCT +3
ATTCACACT +4
ATTCACACT +0
ATTCTACAC +4
ATTCTCAAC +1
ATTCTCAAC +0
ATTCTCACA +1
ATTCTCACA +0
ATTCTCACA
*/
int get_distance(int L, int R) {
if (!is_same_dna(L, R)) return -1;
/// brute force ///
int ans = 0;
deque<int> place[3]; /// ATC
for (int i = L, tok = L; i <= R; ++i) {
while (place[trans[B[i]]].empty()) {
place[trans[A[tok]]].eb(tok), ++tok;
}
int chosen_place = place[trans[B[i]]].front();
// cerr << chosen_place << "\n";
ans += (i - L) - bit_sum(L, chosen_place);
bit_add(chosen_place, 1);
place[trans[B[i]]].pf();
}
for (int i = L; i <= R; ++i) bit_add(i, -1);
return ans;
}
