Background

Abuse of the judging system for this problem will result in an account ban.

Due to technical limitations, please do not submit this problem using the C++ 14 (GCC 9) language option.

This is an interactive problem. You only need to implement the functions required in the code.

Your code does not need to include any extra header files, and you do not need to implement the main function.

Problem Description

Grace is a biologist working at a bioinformatics company in Singapore. Part of her job is to analyze DNA sequences of different organisms. A DNA sequence is a string containing the characters A, T, and C. Note that in this problem, DNA sequences do not contain the character G.

A mutation is defined as swapping the positions of two elements in a DNA sequence. For example, by swapping the bold characters A and C, one mutation can turn ACTA into AATC.

The mutation distance between two sequences is the minimum number of mutations needed to transform one sequence into the other. If it is impossible to transform one sequence into the other using mutations, then the mutation distance between the two sequences is $-1$.

Grace is analyzing two DNA sequences $a$ and $b$, each consisting of $n$ elements, indexed from $0$ to $n - 1$. Your task is to help Grace answer $q$ queries of the following form: what is the mutation distance between the substrings $a[x \ldots y]$ and $b[x \ldots y]$? Here, the substring $s[x \ldots y]$ of a DNA sequence $s$ is defined as the contiguous sequence of characters of $s$ with indices from $x$ to $y$ (including $x$ and $y$). That is, $s[x \ldots y]$ is the sequence $s[x] s[x + 1] \ldots s[y]$.

Input Format

You need to implement the following functions:

void init(string a, string b)

• $a, b$: strings of length $n$, representing the two DNA sequences to be analyzed. This function is called exactly once, and it is called before any call to get_distance.

int get_distance(int x, int y)

• $x, y$: the starting and ending indices of the substring to be analyzed. This function should return the mutation distance between the substrings $a[x \ldots y]$ and $b[x \ldots y]$. This function is called exactly $q$ times.

6 3
ATACAT
ACTATA
1 3
4 5
3 5

2
1
-1

Hint

For all testdata:

• $1 \le n, q \le 100 \, 000$
• $0 \le x \le y \le n - 1$
• Each character of $a$ and $b$ is one of A, T, and C.

Sample Explanation

If the judging program calls get_distance(1, 3), then this call should return the mutation distance between $a[1 \ldots 3]$ and $b[1 \ldots 3]$ (that is, the sequences TAC and CTA). It takes $2$ mutations to turn TAC into CTA: TAC $\to$ CAT, and then CAT $\to$ CTA. It is impossible to complete this transformation with fewer than $2$ mutations.

Therefore, this call should return $2$.

If the judging program calls get_distance(4, 5), then this call should return the mutation distance between the sequences AT and TA. With one mutation, AT can be transformed into TA, and clearly at least one is required.

Therefore, this call should return $1$.

Finally, if the judging program calls get_distance(3, 5), since it is impossible to transform the sequence CAT into ATA using mutations, this call should return $-1$.

Translated by ChatGPT 5