#include "dna.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string A, B;
struct node {
ll val = 0, lz = 0;
bool pd = false;
};
struct stree {
#define lc v*2
#define rc v*2+1
vector <node> tree;
stree (int s) {
tree.resize(s * 4);
}
void pushup(int v) {
tree[v].val = tree[lc].val + tree[rc].val;
}
void pushdown(int v) {
if (!tree[v].pd)
return;
tree[v].pd = false;
tree[lc].pd = tree[rc].pd = true;
tree[lc].val += tree[v].lz;
tree[rc].val += tree[v].lz;
tree[lc].lz += tree[v].lz;
tree[rc].lz += tree[v].lz;
tree[v].lz = 0;
}
void update (int v, int tl, int tr, int l, int r, int val) {
if (tl > r || tr < l)
return;
if (tl >= l && tr <= r) {
tree[v].lz += val;
tree[v].val += val;
tree[v].pd = true;
return;
}
pushdown(v);
int tm = (tl + tr) / 2;
update(lc, tl, tm, l, r, val);
update(rc, tm+1, tr, l, r, val);
pushup(v);
}
ll query(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return 0;
if (tl >= l && tr <= r)
return tree[v].val;
pushdown(v);
int tm = (tl + tr) / 2;
ll a = query(lc, tl, tm, l, r);
ll b = query(rc, tm+1, tr, l, r);
return a + b;
}
};
void init(std::string a, std::string b) {
A = a;
B = b;
}
int get_distance(int x, int y) {
string a = A.substr(x, y - x + 1);
string b = B.substr(x, y - x + 1);
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a != b)
return -1;
a = A.substr(x, y - x + 1);
b = B.substr(x, y - x + 1);
vector <queue <int>> pos(26);
for (int i = 0; i < y - x + 1; i++)
pos[b[i] - 'A'].push(i);
int sz = y - x + 1;
stree tree(sz + 1);
ll ans = 0;
for (int i = 0; i < y - x + 1; i++) {
int j = pos[a[i] - 'A'].front();
pos[a[i] - 'A'].pop();
ll res = 0;
if (i < j)
res = tree.query(1, 0, sz, i, j);
else
res = tree.query(1, 0, sz, j, i);
ans += max(0LL, abs(i - j) - res);
if (i < j)
tree.update(1, 0, sz, i, j, 1);
else
tree.update(1, 0, sz, j, i, 1);
}
return ans;
}
