题目描述

给定一个由字符 $\texttt{A}$、$\texttt{B}$ 和 $\texttt{C}$ 组成的字符串 $s$。

每次操作中，你可以选择字符串中两个相邻的元素 $s_is_{i+1}$，且它们的顺序为以下之一：$\texttt{AB}$、$\texttt{BC}$ 或 $\texttt{CA}$，然后交换它们的位置。

求可以对字符串 $s$ 进行的最大连续操作次数。

本题每个测试包含多组输入数据，你需要分别独立处理每组数据。

输入格式

第一行包含一个整数 $T$ $(1\le T\le 10^5)$ —— 输入数据的组数。接下来是各组数据的描述。

每组数据的第一行包含一个整数 $n$ $(1 \le n \le 10^6)$ —— 字符串 $s$ 的长度。

每组数据的第二行包含一个长度为 $n$ 的字符串 $s$，由字符 $\texttt{A}$、$\texttt{B}$ 和 $\texttt{C}$ 组成。

保证单个测试中所有数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组数据，输出一行一个整数 —— 可以对字符串 $s$ 进行的最大连续操作次数。

输入输出样例 #1

输入 #1

2
5
ABCCA
19
CCAABBBABBAAABBCCAA

输出 #1

3
28

说明/提示

在第一个样例的第一组数据中，字符串 $\texttt{ABCCA}$ 最多可以进行 $3$ 次连续操作。其中一种可能的操作序列是：$[\texttt{ABCCA} \rightarrow \texttt{BACCA}, \texttt{BACCA} \rightarrow \texttt{BACAC}, \texttt{BACAC} \rightarrow \texttt{BAACC}]$。

评分标准

设 $K$ 为单个测试中所有数据的 $n$ 之和。

• （$2$ 分）：答案为 $0$ 或 $1$；
• （$3$ 分）：$n \le 3$；
• （$5$ 分）：对于所有 $1 \le i \le n$，$s_i \ne \texttt{C}$；
• （$5$ 分）：$s$ 的形式为 $\texttt{AA}\ldots \texttt{AABB}\ldots \texttt{BBCC}\ldots \texttt{CC}$（即 $x \cdot \texttt{A} + y \cdot \texttt{B} + z \cdot \texttt{C}$，其中 $x$、$y$、$z$ 为正整数）；
• （$9$ 分）：对于所有 $1 \le i < n$，$s_is_{i+1} \ne \texttt{CA}$；
• （$10$ 分）：$T = 1$，$n \le 12$；
• （$8$ 分）：$n \le 12$；
• （$28$ 分）：$K \le 2000$；
• （$30$ 分）：无额外限制。

#include<bits/stdc++.h>
using namespace std;
int tc;
int n;
const int N=200000;
using ll=long long;
char c[N];
ll dp[N];
int sum[N][3];
ll psum[N][3];
int ed[N],cut[N];
bool check(int l,int r){
	return !((sum[r][2]-sum[l-1][2])&&(sum[r][1]-sum[l-1][1])&&(sum[r][0]-sum[l-1][0]));
}
ll inv(int l,int r,int op1,int op2){//op1>op2
	return psum[l][op1]-psum[r+1][op1]-1ll*(sum[r][op1]-sum[l-1][op1])*(sum[n][op2]-sum[r][op2]);
}
ll cinv(int l,int r){
	if(sum[r][2]-sum[l-1][2]&&sum[r][1]-sum[l-1][1]){
		return inv(l,r,1,2);
	}
	else if(sum[r][2]-sum[l-1][2]&&sum[r][0]-sum[l-1][0]){
		return inv(l,r,2,0);
	}
	else if(sum[r][1]-sum[l-1][1]&&sum[r][0]-sum[l-1][0]){
		return inv(l,r,0,1);
	}
	return 0;
}
void solve(){
	cin>>n;
	fr1(i,1,n){
		cin>>c[i];
		fr1(j,0,2) sum[i][j]=sum[i-1][j];
		sum[i][c[i]-'A']++;
	}
	psum[n+1][0]=psum[n+1][1]=psum[n+1][2]=0;
	fr2(i,n,1){
		fr1(j,0,2) psum[i][j]=psum[i+1][j];
		psum[i][c[i]-'A']+=sum[n][(c[i]-'A'+1)%3]-sum[i][(c[i]-'A'+1)%3];
	}
	int lst=n;
	ed[n]=n;
	fr2(i,n-1,1){
		if(c[i]!=c[i+1]) lst=i;
		ed[i]=lst;
	}
	fr1(i,1,n) dp[i]=-1e18;
	int r=0;
	fr1(l,1,n){
		while(!check(r+1,l)) r++;
		cut[l]=r;
	}
	fr1(i,1,n){
		int tf=cut[i];
		dp[i]=max(dp[tf]+cinv(tf+1,i),dp[i]);
		dp[i]=max(dp[ed[tf+1]]+cinv(ed[tf+1]+1,i),dp[i]);
	}
	cout<<dp[n]<<'\n';
}
int main(){

	ios::sync_with_stdio(false);
	cin>>tc;
	while(tc--) solve();
	ET;
}