自动搬运

查看原文

来自洛谷，原作者为

	Shunpower 我笨笨的，菜菜的，累累的 >_< | 在役

搬运于2025-08-24 23:16:32，当前版本为作者最后更新于2025-07-02 21:46:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题的提交窗口。

最近总是败给这种一个小观察的题。= =

能够重排成回文串，意味着至多一个字符出现了奇数次。我们只需要保留下一个最长的区间使得至多一个字符出现了奇数次。

判掉区间本身就不行，考虑到 Subtask 9 的提示性，我们发现如果没有任何一个字符出现奇数次，删去首尾中的一个就能规约到有一个字符出现了奇数次。

于是考虑有一个字符出现了奇数次怎么做。

有结论：一定删除这个字符偶数次再删恰好一个别的字符。

我们当然也可以删除这个字符奇数次，再删两种别的字符。但这显然是不优的：我要么不必删这个字符奇数次，要么不必多删一种别的字符。

于是只需考虑最少要删这个字符多少次可以删到别的字符。把两头拿出来讨论一下就好了。

int n;
char s[N];
int q;
int nxt[N][26],pre[N][26];
int solve(int l,int r,int c){
	int nl=nxt[l][c];
	int nr=pre[r][c];
	if(r-nr<l+nl) return 0;
	else{
		int ans=0;
		if(!(nl&1)) ans=max(ans,r-l+1-nl-1);
		else if(nr) ans=max(ans,r-l+1-nl-2);
		if(!(nr&1)) ans=max(ans,r-l+1-nr-1);
		else if(nl) ans=max(ans,r-l+1-nr-2);
		return ans;
	}
}
int xr[N];
#define pc __builtin_popcount
int main(){
#ifdef Shun
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	ios::sync_with_stdio(false);	
	cin>>n;
	fr1(i,1,n) cin>>s[i];
	fr1(i,1,n){
		pre[i][s[i]-'a']=pre[i-1][s[i]-'a']+1;
	}
	fr2(i,n,1){
		nxt[i][s[i]-'a']=nxt[i+1][s[i]-'a']+1;
	}
	fr1(i,1,n) xr[i]=xr[i-1]^(1<<s[i]-'a');
	cin>>q;
	while(q--){
		int l,r;
		cin>>l>>r;
		if(pc(xr[r]^xr[l-1])>=2) cout<<r-l+1<<endl;
		else if(pc(xr[r]^xr[l-1])==1) cout<<solve(l,r,__lg(xr[r]^xr[l-1]))<<endl;
		else{
			cout<<max(solve(l+1,r,__lg(xr[r]^xr[l])),solve(l,r-1,__lg(xr[r-1]^xr[l-1])))<<endl;
		}
	}
	ET;
}
//ALL FOR Zhang Junhao.