hugeの张江蔡唐氏模拟赛题解

晚三huge不让去一机房，说便于管理，我的评价是：唐氏
况且二机房没有luogu，改完题后没事干（指写不了狼人），遂写个没人看的题解。
T1 纯哈希，不写。
T2 纯tarjan，一直没学，不写。

T3 比较套路的双指针，赛时降智
题意：给定由 \(B\) 和 \(R\) 组成的字符串，环形结构，每次可以交换相邻，问最少多少次可以将 \(B\) 放到一块，\(R\) 放到一块。多测（范围 \(10^6\)）
阳历

输入
1 
BRRBRRRRBR

输出
3

我们先假设没有环形的交换，那么对于一个序列来说就是在一个分界处，分界左边的 \(B\) 全去左边，右边的全去右边。
显然这个分界是单调的，（因为如果当前分界比上一个不优时，那之后的分界一定严格劣于当前）
然后考虑环形，我们发现环形的交换还是不好处理，于是可以每次枚举环形的断点，对于每个断开的新序列进行如上操作。
显然分界不会受其影响，仍然是单调的。
于是我们复制一遍后进行双指针即可，时间复杂度 \(O(n)\)

#include<bits/stdc++.h>
#define int long long
inline int read(){
	char ch=getchar();int x=0,f=1;
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
const int N=2e6+10;
char s[N];
int num_b[N],num_r[N];
inline int work(int l,int r,int ed){
	int x=ed+1;
	if(s[x]=='R')return 0;
	return (num_r[x]-num_r[l-1])-(num_r[r]-num_r[x-1]);
}
signed main(){
	// freopen("in.in","r",stdin),freopen("out.out","w",stdout);
	std::ios::sync_with_stdio(false);std::cin.tie(0),std::cout.tie(0);
	int T;std::cin>>T;
	while(T--){
		std::cin>>s+1;
		int len=strlen(s+1),n=len*2;
		for(int i=len+1;i<=n;++i)s[i]=s[i-len];
		for(int i=1;i<=n;++i){
			num_b[i]=num_b[i-1];
			num_r[i]=num_r[i-1];
			if(s[i]=='B')num_b[i]++;
			else num_r[i]++;
		}
		int ed=1,r,last_ans=0;
		for(int i=1;i<=len;++i){
			if(s[i]=='B'){
				if(num_r[i]>num_r[len]-num_r[i-1])break;
				last_ans+=num_r[i];
			}
			ed=i;
		}
		for(int i=ed+1;i<=len;++i)
			if(s[i]=='B')last_ans+=num_r[len]-num_r[i-1];
		int ans=last_ans;
		for(int l=2;l<=len;++l){
			r=len+l-1;
			if(s[r]=='B')continue;
			int pd=(num_b[r]-num_b[ed])-(num_b[ed]-num_b[l-1]);
			last_ans=last_ans+pd;
			int zc;
			while((zc=work(l,r,ed))<=0)last_ans+=zc,ed++;
			ans=std::min(last_ans,ans);
		}
		std::cout<<ans<<'\n';
	}
}