GYM103371B Cilantro 做题记录

给定 $n$ 和两个长 $n$ 的 $01$ 串 $S$ 与 $T$。

设入栈序列为 $S$，出栈序列为 $T$ 的所有栈操作序列中，$T_1$ 可能对应的 $S$ 中的下标集合为 $A$。

求 $\sum\limits_{x\in A}x$。

例如 $S=100$，$T=001$ 时答案为 $5$，因为共有 $2$ 种栈操作序列满足入栈序列为 $S$，出栈序列为 $T$：

• 进，进，进，出，出，出，此时 $T_1$ 来自 $S_3$；
• 进，进，出，进，出，出，此时 $T_1$ 来自 $S_2$；

所以答案为 $3+2=5$。

$1\le n\le 5\times 10^6$。

首先有个结论，对于任意两个 $0$ 的个数相等且 $1$ 的个数相等的 $01$ 序列 $A$ 与 $B$，总有合法的栈操作序列满足入栈序列为 $A$ 且出栈序列为 $B$。

证明十分简单，考虑贪心，从左往右逐位考虑 $A$，设当前出栈序列已经匹配 $j$ 个，则若栈顶元素 $x\not=B_{j+1}$ 且 $A_i\not=B_{j+1}$ 则 $A_i$ 入栈， 否则 $j\to j+1$。这样栈中不会同时出现两种不同元素，一定可以构造出来。

考虑从 $1$ 开始，逐个确定 $S_i$ 是否有可能去到 $T_1$。先不考虑 $S_i\not= T_1$ 的情况，那么若 $S_i$ 去了 $T_1$，则 $S_i$ 出栈时 $S_{[1,i-1]}$ 一定都在栈中。

所以可以找到 $i\le j\le pos_{i-1}$ 且 $S_{[i,j]}$ 中 $0$ 的个数等于 $T_{[1,j-i+1]}$ 中 $0$ 的个数的最大的 $j$，令 $pos_i=j$；找不到则 $pos_i=-1$，求出 $pos_i$ 后可以这样构造：

那么显然答案即为 $\sum\limits_{pos_i\not=-1}i$，问题变成求解 $pos_i$，双指针即可，时间复杂度 $O(n)$。

代码如下：

// Problem: B. Cilantro
// Contest: XXII Open Cup, Grand Prix of Korea
// URL: https://codeforces.com/gym/103371/problem/B
// Memory Limit: 1024 MB
// Time Limit: 500 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>

using namespace std;

const int S=5000005;

int n;
char a[S],b[S];
int sa[S],sb[S];
int pos[S];

int main()
{
	scanf("%d",&n);
	scanf("%s%s",a+1,b+1);
	for(int i=1;i<=n;i++) sa[i]=sa[i-1]+(a[i]=='Y'),sb[i]=sb[i-1]+(b[i]=='Y');
	for(int i=1,r=n;i<=n;i++)
	{
		while(r>=i&&sa[r]-sa[i-1]!=sb[r-i+1]) r--;
		pos[i]=r;
	}
	long long ans=0;
	for(int i=1;i<=n;i++) if(pos[i]>=i&&a[i]==b[1]) ans+=i;
	printf("%lld\n",ans);
	return 0;
}