rt，yy了一种 $O(n)$ 的写法，但不知道为何正确，交了一发A了，现在对着 $std$ 拍了 $5000$ 组数据也没错

假如已经能 $O(1)$ 求出每个 R 移到区间两端的代价

如何证明对于每一个枚举的区间，取区间中点时所得答案取 $\min$ 一定是最优的

$\texttt{Code:}$

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define rint register int
#define fill(x,y) memset(x,y,sizeof(x))
#define copy(x,y) memcpy(y,x,sizeof(x))

using namespace std;

inline int read(){
	int w=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
	while(ch>='0'&&ch<='9'){w=(w<<3)+(w<<1)+(ch^48); ch=getchar();}
	return w*f;
}

const int maxn=2e6+5;

int T,n,tot; ll ans=0x7fffffffffffffff;
char s[maxn];
ll bl[maxn],br[maxn],sumr[maxn],sl[maxn],sr[maxn];
inline void init(){
	ans=0x7fffffffffffffff; tot=0;
}
inline ll clac(int l,int k,int r){
	return sl[k]-sl[l-1]-bl[l-1]*(sumr[k]-sumr[l-1])+sr[k+1]-sr[r+1]-br[r+1]*(sumr[r]-sumr[k]);
}
int main(){
	T=read();
	while(T--){
		scanf("%s",s+1); n=strlen(s+1);
		for(int i=1;i<=n;i++) s[i+n]=s[i];
		int len=n; n<<=1;
		for(int i=1;i<=n;i++){
			bl[i]=bl[i-1];
			sl[i]=sl[i-1];
			sumr[i]=sumr[i-1];
			if(s[i]=='B') bl[i]++;
			else{
				sumr[i]++;
				sl[i]+=bl[i];
			}
		}
		for(int i=n;i>=1;i--){
			br[i]=br[i+1];
			sr[i]=sr[i+1];
			if(s[i]=='B') br[i]++;
			else sr[i]+=br[i];
		}
		for(int i=1;i<=len;i++){
			int mid=(i+i+len-1)/2;
			ans=min(ans,clac(i,mid,i+len));
		}
		printf("%lld\n",ans);
		init();
	}
	return 0;
}