题意

给出只包含两种字符的字符串 $s$，可以相邻交换，求把它所有子串变成回文串的代价。

$len \le 7500$

推导

对于一个子串 $s$，由于只有两种字符，其中一种字符满足回文性质后，另一种字符也满足回文，我们这里只考虑字符 $G$。

• 我们不会交换两个相同的字符，交换相同字母字符，则字符串不变，不优。

• 在不交换两个相同字符的情况下，相同字符的顺序不变。也就是说，对于一个子串，第一个 $G$ 对应的是最后一个 $G$，第二个 $G$ 对应的是倒数第二个 $G$。以此类推，除了奇数长度的最中间位置，其他字符都是一一对应的。

• 在一个子串 $s[L,R]$ 中，一对满足回文的位置分别为 $L+x$ 和 $R-x$，满足回文的两个位置 $l$ 和 $r$ 满足 $l+r=L+R$，即确定子串位置时，一对相同的字符使之交换到回文位置的代价是 $|l+r-L-R|$。

回到原问题，只考虑 $G$，可以发现答案的贡献只与子串位置和一对对应字符的位置。

选定一个或两个相邻的 $G$，令其为子串的中心，计算只包含已经选定的 $G$，用维护好的 $l+r$ 统计答案，或 $H$。同时向左右扩展下一个 $G$，再将这两个 $G$ 的位置 $l$ 和 $r$ 的和扔进树状数组维护，由于求的是绝对值，还要维护一下 $l+r$ 和的个数，算那些大于或小于 $L+R$ 的个数，总复杂度 $O(n^{2}\log n)$。

Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=7505;
char a[maxn];
int G[maxn],cnt,len,c[maxn];
struct tree{
	ll c[maxn<<1];
	ll lowbit(int x){return x&-x;}
	inline void add(int x,int y){
		for(int i=x;i<=2*len;i+=lowbit(i))
			c[i]+=y;
	}
	inline ll ask(int x){
		ll sum=0;
		for(int i=x;i;i-=lowbit(i))
			sum+=c[i];
		return sum;
	}
	inline void clear(){
		memset(c, 0, sizeof(c));
	}
}tr1,tr2;
int main(){
	scanf("%s",a+1);
	len=strlen(a+1);
	for(int i=1;i<=len;i++)
		if(a[i]=='G') G[++cnt]=i;//G是 G出现的位置 
	G[0]=0;G[cnt+1]=len+1;
	ll ans=0,sum=0,ansl=0;
	for(int i=1;i<=cnt;++i){	
		int lt=i,rt=i;
		while(lt>=1 && rt<=cnt){
			int qwq = G[lt] + G[rt];
			if(lt!=i) tr1.add(qwq, qwq),tr2.add(qwq,1),sum+=qwq,ansl++;
			for(int l=G[lt];l>G[lt-1];--l)
				for(int r=G[rt];r<G[rt+1];++r){
					if(!((r-l+1)&1)) {ans--;continue;}
					int mid=l+r;
					ll p=tr2.ask(mid-1),q=tr1.ask(mid-1);
					ans+=abs(((l+r)>>1)-G[i]);
					ans+=(p*mid-q)+(sum-q)-(ansl-p)*mid;
				}
			--lt;++rt;
		}
		sum=0;ansl=0;
		tr1.clear();
		tr2.clear();//不同G为中心的子串G的数据是不同的 
	}
	for(int i=1;i<cnt;i++){	
		int lt=i,rt=i+1;
		while(lt>=1 && rt<=cnt){
			int qwq = G[lt] + G[rt]; 
			tr1.add(qwq, qwq),tr2.add(qwq,1);
			sum+=qwq;ansl++;
			for(int l=G[lt];l>G[lt-1];--l)
				for(int r=G[rt];r<G[rt+1];++r){
					int mid=l+r;
					ll p=tr2.ask(mid-1),q=tr1.ask(mid-1);
					ans+=(p*mid-q+(sum-q)-(ansl-p)*mid);
				}
			--lt;++rt;
		}
		sum=0;ansl=0;
		tr1.clear();
		tr2.clear();
	}
	printf("%lld",ans);
	return 0;
}