评测记录

#include <bits/stdc++.h>
using namespace std;

int n; char str[1000002];
int ans = 0;

int x[1000001], y[1000001], z[1000001];
int r1[1000001];
inline bool cmp1(int a, int b){
	return x[a]<x[b];
}
int r2[1000001];
inline bool cmp2(int a, int b){
	return y[r1[a]]<y[r1[b]];
}
void cdq(int l, int r){
	int len = r-l+1;
	if(len<=1) return;
	int mid = (l+r)>>1;
	// 将 x 相等的点全部放在同一边 
	auto range = equal_range(r1+l, r1+r+1, r1[mid], cmp1);
	int midl = range.first-r1, midr = range.second-r1;
	if(midl==l){
		if(midr==r+1) return;
		mid = midr;
	}
	else{
		if(midr-mid<mid-midl) mid = midr;
		else mid = midl;
	}
	// [l, mid) [mid, r]
	int len_l = mid-l, len_r = r-mid+1;
	if(len_l && len_r){
		// 计算右边的点对左边的点的贡献 
		for(int i=0; i!=len; ++i) r2[i] = i+l;
		stable_sort(r2, r2+len, cmp2); // 相同 y 值先统计答案 
		pair<int, int> mmax(0x7fffffff, -1), smax(0x7fffffff, -1); // 最大，次大 
		pair<int, int> mmin(0x7fffffff, 1000007), smin(0x7fffffff, 1000007); // 最小，次小 
		for(int i=0; i!=len; ++i){
			int c = r1[r2[i]];
			int cz = z[c];
			if(r2[i]<mid){
				if(cz!=mmax.first){
					ans = max(ans, mmax.second-c);
				}else{
					ans = max(ans, smax.second-c);
				}
				if(cz!=mmin.first){
					ans = max(ans, c-mmin.second);
				}else{
					ans = max(ans, c-smin.second);
				}
			}else{
				if(cz==mmax.first || cz==smax.first){
					if(cz==mmax.first){
						mmax.second = max(mmax.second, c);
					}else{
						smax.second = max(smax.second, c);
						if(smax.second>mmax.second) swap(mmax, smax);
					}
				}else if(c>mmax.second){
					smax = mmax;
					mmax = {cz, c};
				}else if(c>smax.second){
					smax = {cz, c};
				}
				if(cz==mmin.first || cz==smin.first){
					if(cz==mmin.first){
						mmin.second = min(mmin.second, c);
					}else{
						smin.second = min(smin.second, c);
						if(smin.second>mmin.second) swap(mmin, smin);
					}
				}else if(c<mmin.second){
					smin = mmin;
					mmin = {cz, c};
				}else if(c<smin.second){
					smin = {cz, c};
				}
			}
		}
		
		// 计算左边的点对右边的点的贡献 
		for(int i=0; i!=len; ++i) r2[i] = r-i;
		stable_sort(r2, r2+len, cmp2);
		mmax = {0x7fffffff, -1}; smax = {0x7fffffff, -1};
		mmin = {0x7fffffff, 1000007}; smin = {0x7fffffff, 1000007};
		for(int i=0; i!=len; ++i){
			int c = r1[r2[i]];
			int cz = z[c];
			if(r2[i]>=mid){
				if(cz!=mmax.first){
					ans = max(ans, mmax.second-c);
				}else{
					ans = max(ans, smax.second-c);
				}
				if(cz!=mmin.first){
					ans = max(ans, c-mmin.second);
				}else{
					ans = max(ans, c-smin.second);
				}
			}else{
				if(cz==mmax.first || cz==smax.first){
					if(cz==mmax.first){
						mmax.second = max(mmax.second, c);
					}else{
						smax.second = max(smax.second, c);
						if(smax.second>mmax.second) swap(mmax, smax);
					}
				}else if(c>mmax.second){
					smax = mmax;
					mmax = {cz, c};
				}else if(c>smax.second){
					smax = {cz, c};
				}
				if(cz==mmin.first || cz==smin.first){
					if(cz==mmin.first){
						mmin.second = min(mmin.second, c);
					}else{
						smin.second = min(smin.second, c);
						if(smin.second>mmin.second) swap(mmin, smin);
					}
				}else if(c<mmin.second){
					smin = mmin;
					mmin = {cz, c};
				}else if(c<smin.second){
					smin = {cz, c};
				}
			}
		}
	}
	cdq(l, mid-1);
	cdq(mid, r);
}

int main(){
	scanf("%d%s",&n,str+1);
	for(int i=1,j=1; i<=n; i=j){
		while(j<=n && str[j]==str[i]) ++j;
		ans = max(ans, j-i);
	}
	int B = 0, C = 0, S = 0;
	x[0] = y[0] = z[0] = 0;
	r1[0] = 0;
	for(int i=1; i<=n; ++i){
		if(str[i]=='B') ++B;
		else if(str[i]=='C') ++C;
		else ++S;
		x[i] = B-C;
		y[i] = B-S;
		z[i] = C-S;
		r1[i] = i;
	}
	sort(r1, r1+1+n, cmp1);
	
	cdq(0, n);
	printf("%d", ans);
	return 0;
}