【AtCoder Grand 028E】High Elements 题解

题目大意

  给定一个长度为 $n$ 的排列。
  现在有两个空数组 $X$ 和 $Y$，你要依次把排列的每个元素放到 $X$ 数组或者 $Y$ 数组，使得最后 $X$ 数组和 $Y$ 数组的 high element 个数相同。定义数组中一个元素为 high element 当且仅当它是其前缀最大值。
  一个元素放 $X$ 数组记为 $0$，放 $Y$ 数组记为 $1$，你要求字典序最小的方案，或输出无解。

  $n \leq 2 \times 10^5$

题解

  （看题解学的思路，这里差不多就是把题解翻译了一遍。。。

  首先大的框架肯定是贪心，贪心考虑每一位能不能放 $X$，不行的话能不能放 $Y$。
  所以问题相当于，现在 $X$ 数组里最大值为 $h_X$，high element 数量为 $c_X$，$Y$ 数组里最大值为 $h_Y$，high element 数量为 $c_Y$，排列里剩下的元素是否存在分配方案使得最后 $c_X=c_Y$。

  然后需要观察两条性质：
  1、原排列里的 high element 分配到数组里以后仍然是 high element。（很显然)
  2、假设成功分配的话最后各数组的 high element 长这样：

• $h_X < a_1 < a_2 < \cdots a_x$
• $h_Y < b_1 < b_2 < \cdots b_y$
• 满足 $c_X+x=c_Y+y$

  那么必然存在一种分配方案，使得 $a_1,\cdots,a_x$ 全是原排列的 high element，或使得 $b_1,\cdots,b_y$ 全是原排列的 high element。
  （证明：不然的话，$a_1,\cdots,a_x$ 中存在一项不是原排列的 high element，那把它丢到 $Y$ 数组去它就不产生贡献了，同理也把 $b$ 中的一个非原排列 high element 项丢到 $X$ 去。这样不会破坏 $c_X+x=c_Y+y$ 这条性质。）

  于是首先假设 $a_1,\cdots,a_x$ 全是原排列的 high element（反过来同理）。那么我们只需要考虑 $b_1,\cdots,b_y$ 怎么选，选好之后剩下的 high element 丢给 $X$ 组成 $a_1,\cdots,a_x$，剩下的非 high element 在哪边不产生贡献就留在哪边，即可。
  设排列（当前剩余部分）有 $Q$ 个元素是原来的 high element，那么我们需要选择 $b_1,\cdots,b_y$ 使得 $c_X+Q-k=c_Y+y$，其中 $k$ 表示 $b_1,\cdots,b_y$ 中的原排列 high element 的数量。
  移项得 $c_X-c_Y+Q=y+k=2k+(y-k)$。而等式左边是个定值。这相当于，我从剩余的排列中选一个上升子序列，其中如果这个元素是原排列的 high element 就得 2 分，否则得 1 分，问能否凑出 $c_X-c_Y+Q$ 分。
  再观察发现，如果我有选 1 分元素，所能获得的最大得分是 $m$，那么 $[0,m]$ 这个区间的得分都是可以达到的。如果我只选了 2 分元素，能获得的最大得分是 $m$，那么 $[0,m]$ 这个区间的偶数得分也都是可以达到的。
  因此只需要求最大得分就行了。这是个类似 LIS 的 dp，设 $f_{i,0/1}$ 表示从排列的第 $i$ 项开始，不选 / 选过 1 分元素所能获得的最大得分。
  把这个 dp 值保存在线段树上（$f_{i}$ 的值保存在 $p_i$ 的位置），这样就一边贪心一边询问了，时间复杂度 $O(n \log n)$。

代码

// 自从学了日语，变量名都开始用日语了。。人家日语题面就是“高い項”嘛肯定是用 takai 啦

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=2e5+5;

int n,a[maxn],Q;
bool takai[maxn];

int tr[2][4*maxn];
int tr_cx(int ty,int k,int l,int r,int x)
{
	if (x>n) return 0;
	int re=0;
	while (l<r)
	{
		int t=k<<1, mid=(l+r)>>1;
		if (x<=mid) re=max(re,tr[ty][t+1]), k=t, r=mid;
			else k=t+1, l=mid+1;
	}
	return max(re,tr[ty][k]);
}
void tr_xg(int ty,int k,int l,int r,int x,int z)
{
	if (l==r)
	{
		tr[ty][k]=z;
		return;
	}
	int t=k<<1, mid=(l+r)>>1;
	if (x<=mid) tr_xg(ty,t,l,mid,x,z); else tr_xg(ty,t+1,mid+1,r,x,z);
	tr[ty][k]=max(tr[ty][t],tr[ty][t+1]);
}

bool check(int hx,int hy,int cx,int cy,int ai)
{
	if (ai>hx) hx=ai, cx++;
	int ned=cx-cy+Q;
	if (ned>=0 && (tr_cx(1,1,1,n,hy+1)>=ned || !(ned&1) && tr_cx(0,1,1,n,hy+1)>=ned)) return 1;
	ned=cy-cx+Q;
	if (ned>=0 && (tr_cx(1,1,1,n,hx+1)>=ned || !(ned&1) && tr_cx(0,1,1,n,hx+1)>=ned)) return 1;
	return 0;
}

char ans[maxn];
int main()
{
	scanf("%d",&n);
	int maxa=0;
	fo(i,1,n)
	{
		scanf("%d",&a[i]);
		if (a[i]>maxa)
		{
			takai[i]=1;
			maxa=a[i];
			Q++;
		}
	}
	
	fd(i,n,1)
	{
		int tr0=tr_cx(0,1,1,n,a[i]+1), tr1=tr_cx(1,1,1,n,a[i]+1), f0, f1;
		if (takai[i]) f0=tr0+2, f1=(tr1) ?tr1+2 :0 ;
			else f0=0, f1=max(tr0,tr1)+1;
		tr_xg(0,1,1,n,a[i],f0);
		tr_xg(1,1,1,n,a[i],f1);
	}
	
	int hx=0, hy=0, cx=0, cy=0;
	fo(i,1,n)
	{
		Q-=takai[i];
		tr_xg(0,1,1,n,a[i],0);
		tr_xg(1,1,1,n,a[i],0);
		if (check(hx,hy,cx,cy,a[i]))
		{
			ans[i]='0';
			if (a[i]>hx) hx=a[i], cx++;
		} else if (check(hy,hx,cy,cx,a[i]))
		{
			ans[i]='1';
			if (a[i]>hy) hy=a[i], cy++;
		} else
		{
			puts("-1");
			return 0;
		}
	}
	
	printf("%s\n",ans+1);
}