[DP记录]AT4439 [AGC028E] High Elements
command_block
2021-10-10 21:22:25
**题意** ： 给出一个长度为 $n$ 的排列 $P$ 。
称一个长度为 $n$ 的 $01$ 字符串 $S$ 合法，当且仅当：
初始时有两个空序列 $A,B$ ，按 $i=1\sim n$ 的顺序，若 $S[i]=1$ 则把 $P[i]$ 添加到序列 $A$ 末尾，否则添加到序列 $B$ 末尾。最终 $A,B$ 的前缀最大值个数相等。
求字典序最小的合法字符串 $S$。
$n\le 2\times 10^5$ ，时限$\texttt{2s}$。
------------
考虑经典的按位贪心 ： 从前往后处理，每次判定填 $0$ 后是否有解，能填 $0$ 则填 $0$ 。
问题转化为对 $S$ 逐位确定，并判定是否有解。
记 $pre(A)$ 为序列 $A$ 的前缀最大值集合。
不难发现，对于 $p\in pre(P)$ ，$p$ 在分到 $A,B$ 中之后也必然成为前缀最大值。
- **性质** ： 对于一个确定的前缀 $S[1,i]$ ，若存在合法的补完方案，则一定有一种方案满足 $pre(A)_{\rm new}\subseteq pre(P)$ 或者 $pre(B)_{\rm new}\subseteq(P)$。
其中 $pre(A)_{\rm new}$ 指 $A$ 新增的前缀最大值。
- **证明** ：
若存在 $a\in pre(A),\ b\in pre(B)$ ，满足 $a,b\notin pre(P)$ ，考虑将两者交换，注意到使得 $a,b$ 在 $P$ 中不为前缀最大值的元素一定存在于 $B,A$ （另一个序列）中，所以交换后两者都不再是前缀最大值。
$A,B$ 的前缀最大值个数同时减一，仍然满足条件。可以不断进行该类交换，即可得到满足性质的解。
（这里利用了判定子问题的特性，按需推理。若直接考虑刻画答案的性质，则较为吃力）
现在我们已经填写了 $S[1,i]$ ，需要判定否可行。
分别考虑 $pre(A)_{\rm new}\subseteq pre(P)$ 或者 $pre(B)_{\rm new}\subseteq(P)$ ，下文只介绍 $pre(A)_{\rm new}\subseteq pre(P)$ 的情况。
记目前 $A,B$ 中的最大值分别为 $x_A,x_B$ ，前缀最大值个数分别为 $c_A,c_B$ ， $k_i=pre(P)∩P[i,n]$ 。
设 $|pre(B)_{\rm new}|=s_0+s_1$ ，其中 $s_0$ 为非 $pre(P)$ 中的元素个数，$s_1$ 为 $pre(P)$ 中的元素个数。
则有 ：
$$c_A+k_i-s_1=c_B+s_0+s_1$$
$$c_A+k_i-c_B=s_0+2s_1$$
此时左侧 $c_A+k_i-c_B$ 是个常数，只需判定是否存在一种 $pre(B)_{\rm new}$ 使得 $s_0+2s_1$ 满足条件。
即 ： 令 $pre(P)$ 中元素权值为 $2$ ，其余元素权值为 $1$ ，判定 $P[i,n]$ 中能否选出上升子序列使得权值和为给定值，且首元素 $> x_B$ 。
不难发现，若能得到权值和为 $s$ 的上升子序列，那么通过除去最小权值一定能得到权值和为 $s-2$ 的，故只需记录奇偶最大值。
考虑 DP ，记 $dp[i,0/1]$ 表示后缀 $P[i,n]$ 中和为 奇/偶 的最大值，且必选 $P[i]$ ，此时 $P[i]$ 恰为上升子序列中最小值。
转移如下 ：
$$dp[i,k]=w_i+\max\limits_{j=i+1}^n[P_j>P_i]dp[j,(k+w_i)\bmod 2]$$
容易线段树优化。
在判定时，需要查询后缀 $P[i,n]$ 中值 $>x$ ，奇偶性为 $c$ 的上升子序列的最大权值。即
$$\max_{i\leq j}[P_j>x]dp[i,c]$$
这个也可以用线段树优化计算。
复杂度 $O(n\log n)$。
```cpp
#include<algorithm>
#include<cstdio>
#define MaxN 200500
using namespace std;
const int INF=1000000000;
int n;
#define lbit(p) (p&-p)
struct MaxDS
{
int a[MaxN<<2],to,wfc,ret;
void Init()
{for (int i=1;i<=(n+1)*4;i++)a[i]=-INF;}
void chg(int l,int r,int u)
{
if (l==r){a[u]=wfc;return ;}
int mid=(l+r)>>1;
if (to<=mid)chg(l,mid,u<<1);
else chg(mid+1,r,u<<1|1);
a[u]=max(a[u<<1],a[u<<1|1]);
}
void chg(int p,int x)
{to=p;wfc=x;chg(1,n+1,1);}
void qry(int l,int r,int u)
{
if (to<=l){ret=max(ret,a[u]);return ;}
int mid=(l+r)>>1;
if (to<=mid)qry(l,mid,u<<1);
qry(mid+1,r,u<<1|1);
}
int qry(int p)
{to=p;ret=-INF;qry(1,n+1,1);return ret;}
}T[2];
int p[MaxN],x0,x1,c0,c1,o[MaxN];
bool fl[MaxN];char ans[MaxN];
bool chk(int i)
{
int c=c0+o[i]-c1;
if (c>=0&&T[c&1].qry(x1+1)>=c)return 1;
c=c1+o[i]-c0;
if (c>=0&&T[c&1].qry(x0+1)>=c)return 1;
return 0;
}
int main()
{
scanf("%d",&n);
for (int i=1,las=0;i<=n;i++){
scanf("%d",&p[i]);
if (p[i]>las){fl[i]=1;las=p[i];}
}
T[0].Init();T[1].Init();T[0].chg(n+1,0);
for (int i=n;i;i--){
int det=(fl[i] ? 2 : 1),dp[2];
dp[0]=det+T[det&1].qry(p[i]);
dp[1]=det+T[(det+1)&1].qry(p[i]);
T[0].chg(p[i],dp[0]);
T[1].chg(p[i],dp[1]);
}
for (int i=n;i;i--)o[i]=o[i+1]+fl[i];
if (!chk(1)){puts("-1");return 0;}
for (int i=1;i<=n;i++){
T[0].chg(p[i],-INF);T[1].chg(p[i],-INF);
int _x0=x0,_c0=c0;
if (p[i]>x0){x0=p[i];c0++;}
if (chk(i+1))ans[i]='0';
else {
ans[i]='1';x0=_x0;c0=_c0;
if (p[i]>x1){x1=p[i];c1++;}
}
}puts(ans+1);
return 0;
}
```