双指针想法WA ON Test26
查看原帖
双指针想法WA ON Test26
575363
revolutionary_oier楼主2024/7/15 16:35
#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int maxn=2e6+10;
int n,ans,cnt;
char a[maxn];
int f3[maxn],f2[maxn],f1[maxn],pre[maxn],nxt[maxn],op[maxn];
inline void ipt(){
	scanf("%s",a);
	n=strlen(a);
	for(int i=n;i>=1;i--)a[i]=a[i-1];
	for(int i=1;i<=n;i++){
		if(a[i]=='@')op[++cnt]=i;
	}
}
inline void init(){
	for(int i=1;i<=n;i++){
		f3[i]=f3[i-1];
		if(a[i]!='@'&&a[i]!='.')f3[i]++;
	}
	for(int i=1;i<=n;i++){
		f2[i]=f2[i-1];
		if(a[i]!='@'&&a[i]!='.'&&a[i]!='_')f2[i]++;
	}
	for(int i=1;i<=n;i++){
		f1[i]=f1[i-1];
		if(a[i]>='a'&&a[i]<='z')f1[i]++;
	}
	for(int i=2;i<=n;i++){
		if(a[i-1]!='@'&&a[i-1]!='.')pre[i]=pre[i-1]+1;
	}
	for(int i=n-1;i>=1;i--){
		if(a[i+1]>='a'&&a[i+1]<='z')nxt[i]=nxt[i+1]+1;
	}
}
inline void solve(){
	int l,r=1;
	for(int i=1;i<=cnt;i++){	
        l=op[i];
		r=max(r,l+1);
		while(a[r]!='.'&&r<=n)++r;
		if(r>n)break; 
		int u=f2[r-1]-f2[l]+1,s=-1,t=-1;
		if(u!=r-l)continue;
		s=l-pre[l];
		t=r+nxt[r];
		if(t==-1||s==-1)continue;
		ans=ans+(f1[l-1]-f1[s-1])*(t-r);
	}
	printf("%lld\n",ans);
}
signed main(){
	ipt();
	init();
	solve();
	return 0;
}
2024/7/15 16:35
加载中...