非常好的前缀和入门题（逃

一句话题解：咋做都行。我们考虑把 ATC 和所有要替换的信息（例如 A->C A->T）记录前缀和，查询时先对换（例如 A->T, T->A），剩余的三轮换（例如 A->T, T->C, C->A）即可。

代码：

//By rui_er
#include "dna.h"
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
const int N = 1e5+5;

std::string s, t;
int n, preS[N][3], preT[N][3], pre[N][3][3], now[3][3];
void init(std::string a, std::string b) {
	s = a; t = b;
	n = s.length();
	for(int i=0;i<n;i++) {
		if(s[i] == ‘T‘) s[i] = ‘B‘;
		if(t[i] == ‘T‘) t[i] = ‘B‘;
	}
	++preS[0][s[0]-‘A‘];
	++preT[0][t[0]-‘A‘];
	++pre[0][s[0]-‘A‘][t[0]-‘A‘];
	for(int i=1;i<n;i++) {
		for(int j=0;j<3;j++) {
			for(int k=0;k<3;k++) {
				pre[i][j][k] = pre[i-1][j][k];
			}
		}
		++pre[i][s[i]-‘A‘][t[i]-‘A‘];
		for(int j=0;j<3;j++) {
			preS[i][j] = preS[i-1][j];
			preT[i][j] = preT[i-1][j];
		}
		++preS[i][s[i]-‘A‘];
		++preT[i][t[i]-‘A‘];
	}
}

int get_distance(int x, int y) {
	for(int i=0;i<3;i++) {
		int A = preS[y][i] - (x ? preS[x-1][i] : 0);
		int B = preT[y][i] - (x ? preT[x-1][i] : 0);
		if(A != B) return -1;
	}
	for(int i=0;i<3;i++) {
		for(int j=0;j<3;j++) {
			now[i][j] = pre[y][i][j] - (x ? pre[x-1][i][j] : 0);
		}
	}
	int ans = 0;
	for(int i=0;i<3;i++) {
		for(int j=i+1;j<3;j++) {
			int mn = std::min(now[i][j], now[j][i]);
			now[i][j] -= mn;
			now[j][i] -= mn;
			ans += mn;
		}
	}
	assert(now[0][1]==now[1][2]&&now[1][2]==now[2][0]);
	assert(now[2][1]==now[1][0]&&now[1][0]==now[0][2]);
	ans += 2 * (now[0][1] + now[1][0]);
	return ans;
}
/*
int main() {
	int n, q;
	std::cin>>n>>q;
	std::string a, b;
	std::cin>>a>>b;
	init(a, b);
	for(int i=0;i<q;i++) {
		int x, y;
		std::cin>>x>>y;
		std::cout<<get_distance(x, y)<<std::endl;
	}
	return 0;
}*/

[IOI2021D2T1] dna 简要题解