自动搬运

查看原文

来自洛谷，原作者为

	Deer_Peach Huh？||潜水ing~||私信前请看注意事项

搬运于2025-08-24 23:13:59，当前版本为作者最后更新于2025-04-19 18:26:02，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：

给你一个长度为 $n$ 的只包括 $\texttt{v}$、$\texttt{a}$、$\texttt{n}$ 三个字符的字符串，有 $m$ 次操作，每次操作交换 $s_x$ 和 $s_{x+1}$，求每次操作后字符串中 $\texttt{van}$ 作为子序列的出现次数。

思路：

暴力解法直接排除，思考怎么快速计算。

我们可以寻找每一个字符 $\texttt{a}$，统计其前面的 $\texttt{v}$ 以及后面 $\texttt{n}$ 的数量，相乘便是含有这个 $\texttt{a}$ 的子序列的数量，累加便是最后的答案。

再考虑修改，每次修改只会交换前后的字符，重要的是，每次修改只会影响一个 $\texttt{a}$ 前后 $\texttt{v}$ 和 $\texttt{n}$ 的数量。 具体需要分类讨论：

1. $s_x$ 为字符 $\texttt{a}$；
2. $s_x$ 为字符 $\texttt{v}$；
3. $s_x$ 为字符 $\texttt{n}$。

当 $s_x$ 为字符 $\texttt{a}$ 时，讨论 $s_{x+1}$：

1. $s_{x+1}$ 为字符 $\texttt{x}$，则相当于没修改；
2. $s_{x+1}$ 为字符 $\texttt{v}$，则 $\texttt{a}$ 前面 $\texttt{v}$ 的数量加一；
3. $s_{x+1}$ 为字符 $\texttt{n}$，则 $\texttt{a}$ 后面 $\texttt{n}$ 的数量减一。

当 $s_{x+1}$ 为字符 $\texttt{a}$ 时，讨论 $s_{x}$：

1. $s_{x}$ 为字符 $\texttt{x}$，同上；
2. $s_{x}$ 为字符 $\texttt{v}$，则 $\texttt{a}$ 前面 $\texttt{v}$ 的数量减一；
3. $s_{x}$ 为字符 $\texttt{n}$，则 $\texttt{a}$ 后面 $\texttt{n}$ 的数量加一。

都不是则没有影响，因为只有当 $\texttt{a}$ 是被修改的两个字符中其中一个才会受到影响，具体证明很简单，不再赘述。

每次修改减去当前 $\texttt{a}$ 的贡献，再更新前后 $\texttt{v}$ 和 $\texttt{n}$ 的数量，最后加上更新后 $\texttt{a}$ 的贡献就是最后的答案。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=1e6+5;
int n,m;
string s;
int va[N],an[N];
vector<int>a;
int numa;
signed main(){
    IOS;
    cin>>n>>m;
    cin>>s;
    s=" "+s;
    int numv=0,numn=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='v')numv++;
		if(s[i]=='a'){
			va[i]=numv;
			a.push_back(i);
			numa++;
		}
	}
	for(int i=n;i>=1;i--){
		if(s[i]=='n')numn++;
		if(s[i]=='a'){
			an[i]=numn;
		}
	}
	int ans=0;
	for(int i=0;i<numa;i++){
		ans=ans+va[a[i]]*an[a[i]];
	}
	while(m--){
		int x;
		cin>>x;
		int l=0,r=numa-1;
		int mid;
		while(l<r){
			mid=l+r>>1;
			a[mid]>=x?r=mid:l=mid+1;
		}
		int aid=a[r];
		if(aid==x){
			if(s[x+1]=='a'){
				cout<<ans<<endl;
			}
			if(s[x+1]=='v'){
				ans=ans-va[x]*an[x];
				swap(va[x],va[x+1]);
				swap(an[x],an[x+1]);
				va[x+1]++;
				ans=ans+va[x+1]*an[x+1];
				a[r]++;
				cout<<ans<<endl;
			}
			if(s[x+1]=='n'){
				ans=ans-va[x]*an[x];
				swap(va[x],va[x+1]);
				swap(an[x],an[x+1]);
				an[x+1]--;
				ans=ans+va[x+1]*an[x+1];
				a[r]++;
				cout<<ans<<endl;
			}
		}
		else if(aid==x+1){
			if(s[x]=='v'){
				ans=ans-va[x+1]*an[x+1];
				swap(va[x],va[x+1]);
				swap(an[x],an[x+1]);
				va[x]--;
				ans=ans+va[x]*an[x];
				a[r]--;
				cout<<ans<<endl;
			}
			if(s[x]=='n'){
				ans=ans-va[x+1]*an[x+1];
				swap(va[x],va[x+1]);
				swap(an[x],an[x+1]);
				an[x]++;
				a[r]--;
				ans=ans+va[x]*an[x];
				cout<<ans<<endl;
			}
		}
		else{
			cout<<ans<<endl;
		}
		swap(s[x],s[x+1]);
		/*cout<<s<<endl;
		for(int i=1;i<=numa;i++){
			cout<<a[i-1]<<" ";
			cout<<va[a[i-1]]<<" "<<an[a[i-1]]<<endl;
		}*/
	}
	return 0;
}

很明显可以优化，但作者懒得优化（疑似最劣解）。