AGC028E High Elements 做题记录

给定一个 $n$ 的排列 $P$，一个长 $n$ 的 01 串 $S$ 合法当且仅当：

• 设 $A$ 为所有 $S_i=1$ 的 $a_i$ 构成的子序列，$B$ 为所有 $S_i=0$ 的 $a_i$ 构成的子序列，则 $A$ 和 $B$ 的前缀最大值个数相等；

求所有合法的 $S$ 中字典序最小的那个。

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

显然 $P$ 中的前缀最大值在 $A$ 和 $B$ 中还是前缀最大值，那么不妨将在 $P$ 中就是前缀最大值的数称为“旧的”，在 $P$ 中不是但在 $A$ 或 $B$ 中是前缀最大值的数成为“新的”。

那么有个结论：

若合法的 $S$ 存在，那么一定存在某个合法的 $S$ 满足 $A$ 中的前缀最大值都是旧的。

那么考虑贪心，从前往后枚举 $S$ 的每个位，判断这一位填 $0$ 后还存不存在合法的 $S$ 即可。

设当前填完了 $S_{[1,i]}$，$A$ 共有 $cx$ 个前缀最大值，当前最大值为 $mx$；$B$ 共有 $cy$ 个前缀最大值，当前最大值为 $my$，$P_{[i+1,n]}$ 中一共有 $c$ 个旧的前缀最大值。

不妨假设 $A$ 之后的前缀最大值全都是旧的，那么设 $B$ 后面共有 $k$ 个旧的前缀最大值和 $m$ 个新的前缀最大值，则当前填法合法当且仅当有：

$\begin{aligned} cx+c-k&=cy+k+m\\ m+2k&=cx+c-cy \end{aligned}$

$cx+c-cy$ 是已知的，那么只要判断 $m+2k$ 是否能满足即可。

而这就相当于给旧的前缀最大值赋一个 $2$ 的权值，其它数赋 $1$，求能否在 $P_{[i+1,n]}$ 中找到一个严格上升子序列 $R$ 满足 $R_1>my$ 且 $R$ 的权值和为 $cx+c-cy$。

不难发现若找到了权值和为 $x$ 的严格上升子序列，则一定能找到权值和为 $x-2$ 的。所以找到权值和为奇数/偶数的最大的权值和即可。

那么使用值域线段树维护，先倒着扫一遍求出 $f_{i,0/1}$ 表示以 $i$ 开头的权值和为偶数/奇数的严格上升子序列的最大的权值和，在贪心的时候每次把 $f_{P_i}$ 删掉即可。

时间复杂度 $O(n\log n)$，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=200005;

struct segment
{
	int mx[S<<2];
	inline void upda(int u)
	{
		mx[u]=max(mx[u<<1],mx[u<<1|1]);
	}
	void upd(int u,int l,int r,int p,int x)
	{
		if(l==r) return mx[u]=x,void();
		int mid=l+r>>1;
		if(p<=mid) upd(u<<1,l,mid,p,x);
		else upd(u<<1|1,mid+1,r,p,x);
		upda(u);
	}
	int que(int u,int l,int r,int L,int R)
	{
		if(l>R||r<L) return -1e8;
		if(l>=L&&r<=R) return mx[u];
		int mid=l+r>>1,res=-1e8;
		if(L<=mid) res=max(res,que(u<<1,l,mid,L,R));
		if(R>=mid+1) res=max(res,que(u<<1|1,mid+1,r,L,R));
		return res;
	}
}tr[2];

int n,a[S];
bool flg[S];
int ans[S];

inline bool chk(int x,int val)
{
	if(val<0) return false;
	return tr[val&1].que(1,1,n,x,n)>=val;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1,mx=0;i<=n;i++)
	{
		flg[i]=a[i]>mx;
		mx=max(mx,a[i]);
	}
	for(int i=1;i<=n;i++) tr[1].upd(1,1,n,i,-1e8);
	for(int i=n;i>=1;i--)
	{
		int p0=tr[0].que(1,1,n,a[i],n);
		int p1=tr[1].que(1,1,n,a[i],n);
		if(flg[i])
		{
			tr[0].upd(1,1,n,a[i],p0+2);
			tr[1].upd(1,1,n,a[i],p1+2);
		}
		else
		{
			tr[0].upd(1,1,n,a[i],p1+1);
			tr[1].upd(1,1,n,a[i],p0+1);
		}
	}
	int c=0;
	for(int i=1;i<=n;i++) c+=flg[i];
	int cx=0,cy=0,mx=0,my=0;
	for(int i=1;i<=n;i++)
	{
		c-=flg[i];
		tr[0].upd(1,1,n,a[i],0);
		tr[1].upd(1,1,n,a[i],-1e8);
		int nx=cx+(a[i]>mx);
		int valx=nx+c-cy;
		int valy=cy+c-nx;
		if(chk(my,valx)||chk(max(mx,a[i]),valy))
		{
			ans[i]=0;
			cx+=a[i]>mx;
			mx=max(mx,a[i]);
		}
		else
		{
			ans[i]=1;
			cy+=a[i]>my;
			my=max(my,a[i]);
		}
	}
	if(cx!=cy) return puts("-1"),0;
	for(int i=1;i<=n;i++) putchar(ans[i]+'0');
	printf("\n");
	return 0;
}