自动搬运

查看原文

来自洛谷，原作者为

	vectorwyx 打 OI 就像心跳一样自然，退役就像去世一样必然。

搬运于2025-08-24 22:43:38，当前版本为作者最后更新于2022-12-24 22:25:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考虑对于整个数组怎么求出最小代价。

首先如果 $0,1$ 均出现了奇数次那么它不可能重排为回文串，直接贡献 $-1$。否则令 $m$ 表示 $1$ 的个数，考虑每个 $1$ 最终去到了哪。假设最初 $1$ 所在位置构成的序列 $a$，最终 $1$ 所在位置构成的序列为 $b$，那么这是一个类似匹配的问题，贪心，把 $a,b$ 从小到大排序后 $\sum |a_i-b_i|$ 即为答案。

$a$ 是固定的，现在的问题是如何设置 $b$ 使得 $\sum |a_i-b_i|$ 最小。注意到 $b_{i}+b_{m-i+1}=r-l+2$，那只要确定了 $b$ 的前半边就确定了整个 $b$。于是每次可以匹配掉首尾的一对元素，不难想到 dp，记 $f(i,j)$ 表示当前推到 $i$ 这个位置匹配掉了 $j$ 对 $1$ 的最小代价，转移是 $f(i,j)=\min(f(i-1,j),f(i-1,j-1)+|i-a_i|+|n-i+1-a_{m-i+1}|)$。最终答案为 $f_{n/2,m/2}$。当然在 $m$ 为奇数时需要特殊处理中心点，它的贡献恒为 $|\frac{n+1}{2}-a_{\frac{m+1}{2}}|$。至此我们得到了一个 $O(n^4)$ 的做法，可以通过前三个点。

接下来优化这个 dp，有个显然的想法是对每个 $a_i(i\le \frac{m}{2})$ 取匹配点 $i$ 使得 $|i-a_i|+|n-i+1-a_{m-i+1}|$ 最小，问题在于这样取出来的 $b_i$ 可能不单调。注意到 $|i-a_i|+|n-i+1-a_{m-i+1}|=|i-a_i|+|i-(n+1-a_{m-i+1})|$，那么当 $i$ 落在 $[a_i,n+1-a_{m-i+1}]$ 时式子取得最小值。考虑 $a$ 的前半边是否落在 $\frac{n}{2}$ 左边，如果是，令 $b_i=a_i$ 即满足条件。否则，令 $b_i=n+1-a_{m-i+1}$ 则满足条件。那么答案即为 $\sum_i |a_i+a_{m-i+1}-(n+1)|$，不需要 dp。复杂度变为 $O(n^3)$，可以通过前五个点。

然后转为枚举 $a_i,a_{m-i+1}$ 计算它们配对产生的贡献。还是记 $a$ 为整个数组中 $1$ 的位置序列，如果两个位置 $a_i,a_j$ 想要配对的话首先有 $l\le a_i,r\ge a_j$，同时如果 $j-i+1$ 为奇数那么 $r-l+1$ 应当也为奇数。对于每个合法的 $l,r$，$a_i,a_j$ 的贡献为 $|a_i+a_j-(l+r)|$。如果事先知道所有 $[l,r]$ 的信息是不是就好办了，不难发现 $i,j$ 对应的信息可以由 $i-1,j+1$ 递推而来。那么考虑从 $a$ 的每段前缀以及每段后缀出发，每次砍掉首尾的两个元素，把新产生的 $[l,r]$ 加进一个数据结构里。而这里新产生的 $[l,r]$ 其实就是 $l\in(a_{i-1},a_i],r\in[a_j,a_{j+1})$ 对应的所有区间，于是可以枚举 $l+r$ 简单地算出 $l+r$ 的出现次数，然后一并插入数据结构。

现在看看这个数据结构需要支持什么：维护一个可重集，支持：插入 $c$ 个 $x$，查询所有 $\le x$ 的元素之和以及元素个数。由于 $x\le 2n$，只需要用一个树状数组。复杂度 $O(n^2\log n)$。有一个细节是让出现次数较少的值作为 $1$，这样可以省去一半的常数。

代码如下：（码字不易，能不能点个赞再走QAQ）

#include<bits/stdc++.h>
namespace vectorwyx{
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define uint unsigned
#define ull unsigned long long
#define umap unordered_map
#define db double
#define fo(i,x,y) for(int i=(x);i<=(y);++i)
#define go(i,x,y) for(int i=(x);i>=(y);--i)
#define ptc putchar
#define emp emplace
#define re return
#define co continue
#define brk break
#define HH (ptc('\n'))
#define bctz __builtin_ctz
#define bclz __builtin_clz
#define bppc __builtin_popcount
using namespace std;
ll seed=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
inline int rm(int x,int y){return (int)(rnd()%(y-x+1ll)+x);}
inline int read(){signed ch=getchar();int x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void out(int *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}

const int N=7505,inf=1e9;
int cnt;ll sum;
namespace BIT{
int n;
pair<int,ll> tr[N<<1];
#define lbit(x) (x&(-x))
void upd(int c,int k){//插入 c 个 k 
//	printf("upd(%d,%d)\n",c,k);
	sum+=(ll)c*k;cnt+=c;
	int x=k;
	while(x<=n){
		tr[x].fi+=c,tr[x].se+=(ll)c*k;
		x+=lbit(x);
	}
}
int ask_cnt(int x){
	int ret=0;
	while(x){
		ret+=tr[x].fi;
		x-=lbit(x);
	}
	re ret;
}
ll ask_sum(int x){
	ll ret=0;
	while(x){
		ret+=tr[x].se;
		x-=lbit(x);
	}
	re ret;
}
void clear(){fo(i,1,n) tr[i]=mk(0,0);}
}
using BIT::upd;
using BIT::ask_cnt;
using BIT::ask_sum;
using BIT::clear;


int a[N],n,c0[N],c1[N],b[N],m,pos[N],ct;
ll ans;

inline void play(int l,int r,int L,int R,bool fl){
	r-=l,R-=L;
	fo(x,0,r+R) if(!fl||(x+l+L)%2==0){
		int lx=max(0,x-R),rx=min(x,r);
//		int c=fl?(rx/2-(lx-1)/2):(rx-lx+1);
		int c=(rx-lx+1);
		upd(c,x+l+L);
	}
}

void shrink(int l,int r){
	int fl=(r-l+1)&1;
	sum=0;cnt=0;
	clear();
	while(l<=r){
//		printf("[%d,%d]\n",l,r);
//		fo(j,pos[l-1]+1,pos[l]) fo(k,pos[r],pos[r+1]-1) 
//			if(!fl||((k-j+1)&1)) upd(1,j+k),sum+=j+k,cnt++;
		play(pos[l-1]+1,pos[l],pos[r],pos[r+1]-1,fl);
		int x=pos[l]+pos[r];
		ll val=sum-2*ask_sum(x)+(ll)x*(2*ask_cnt(x)-cnt);
//		printf("cnt=%d sum=%lld x=%d val=%lld\n",cnt,sum,x,val);
		if(l==r){
			assert(val%2==0);
			ans+=val/2;
		}else ans+=val;
//		printf("now ans=%lld\n",ans);
		l++,r--;
	}	
}

signed main(){
	int ch=getchar();while(ch!='G'&&ch!='H') ch=getchar();
	while(ch=='G'||ch=='H') a[++n]=ch=='G',ch=getchar();
	{
		int c=0;fo(i,1,n) c+=a[i];
		if(c>n/2) fo(i,1,n) a[i]^=1;
	}
	BIT::n=2*n;
//	cout<<n<<'\n';out(a,1,n);
	fo(i,1,n){
		c0[i]=c0[i-1]+(a[i]==0);
		c1[i]=c1[i-1]+(a[i]==1);
	}
	fo(i,1,n) if(a[i]) pos[++ct]=i;
	pos[ct+1]=n+1;
//	cout<<"pos:";out(pos,0,ct+1);
	fo(i,1,ct) shrink(1,i);
	fo(i,2,ct) shrink(i,ct);
	fo(l,1,n) fo(r,l+1,n){
		int x=c0[r]-c0[l-1],y=c1[r]-c1[l-1];
		if((x&1)&&(y&1)) ans--;
	}	
	cout<<ans;
	return 0;
}
}
/*
GHHGGHHGH
-------------------------------------------------
12
*/










signed main(){re vectorwyx::main();}