被动态逆序对戏耍，来写博客这次考试油炸了
模板爆零，哈希调半天导致T3没时间，我都干了些什么&_&
T3思路：
利用环的性质先拼成一条链，然后二分边界。
证明就不说啦（其实是我不会）
AC代码：
1 #include<bits/stdc++.h> 2 #define MAXN 2000005 3 #define ll long long 4 using namespace std; 5 ll s[MAXN],num,L[MAXN],lsum[MAXN],rsum[MAXN],R[MAXN],fosum[MAXN]; 6 ll ans; 7 void Rd() 8 { 9 char c=getchar(); 10 while(c!='B'&&c!='R')c=getchar(); 11 while(c=='B'||c=='R'){if(c=='B')s[++s[0]]=0,num++;else s[++s[0]]=1;c=getchar();} 12 return ; 13 } 14 ll Getl(int l,int r) 15 { 16 return lsum[r]-lsum[l-1]-L[l-1]*(r-l+1-fosum[r]+fosum[l-1]); 17 } 18 ll Getr(int l,int r) 19 { 20 return rsum[l]-rsum[r+1]-R[r+1]*(r-l+1-fosum[r]+fosum[l-1]); 21 } 22 ll calc(int l,int r,int x) 23 { 24 return Getl(l,x)+Getr(x+1,r); 25 } 26 int main() 27 { 28 int t,p; 29 scanf("%d",&t); 30 while(t--) 31 { 32 p=1;ans=0x7f7f7f7f7f7f7f;s[0]=0;num=0; 33 Rd(); 34 num/=2; 35 for(int i=1;i<=s[0];i++)s[i+s[0]]=s[i]; 36 for(int i=1;i<=2*s[0];i++) 37 { 38 if(s[i]^1)fosum[i]=fosum[i-1]+1,L[i]=L[i-1]+1; 39 else fosum[i]=fosum[i-1],L[i]=L[i-1]; 40 if(s[i]^0)lsum[i]=lsum[i-1]+L[i]; 41 else lsum[i]=lsum[i-1]; 42 } 43 for(int i=2*s[0];i>=1;i--) 44 { 45 if(s[i]^1)R[i]=R[i+1]+1; 46 else R[i]=R[i+1]; 47 if(s[i]^0)rsum[i]=rsum[i+1]+R[i]; 48 else rsum[i]=rsum[i+1]; 49 } 50 for(int i=1;i<=s[0];i++) 51 { 52 if(s[i]==0)continue; 53 while(fosum[p]-fosum[i-1]<=num)p++; 54 ans=min(ans,calc(i,i+s[0]-1,p)); 55 } 56 printf("%lld\n",ans); 57 } 58 return 0; 59 }