[AGC028E] High Elements 题解
好久没写题解了，落实的时候这道题搞了一下午，就正好写下吧。
题意
洛谷界面
让我学懂了的博客
给定一个 \(1\sim n\) 的排列 \(P\) ，求字典序最小的 \(0,1\) 串 \(S\) 满足：
- 先设两个空序列 \(A,B\)，我们按照 \(1\) 到 \(n\) 的顺序，若 \(S_i\) \(=1\) 则把 \(P_i\) 添加到序列 \(A\) 的末尾，否则添加到序列 \(B\) 的末尾，使得 \(A,B\) 的前缀最大值个数相等。
\(n\le 2\cdot 10^5\)
题解
先来分析前缀最大值的来源： \(P\) 中的前缀最大值无论到了哪个序列都是前缀最大值，这毫无疑问。而有一些在 \(P\) 中不是前缀最大值的数，到了一个序列中因为前面比它大的数到了另一个序列而成了前缀最大值。我们称前者为“旧的”，后者为“新的”
然后考虑 字典序最小 ，根据套路逐位贪心，只需要逐位判断“这样”填了第 \(i\) 位之后能否合法，而不需要管后面此时是否最小。
现在来说一个结论：如果当前的 \(A,B\) 前缀合法，则一定存在一个合法的 \(S\) 使得其中一个串还没填的部分只有旧的前缀最大值，反之也成立。
证明：如果两个串没填的部分都有新的前缀最大值，那么一边抽出一个数，设为 \(a,b\) ，它们在 \(P\) 中前面比它们大的数都会在另一个串中，把 \(a,b\) 交换一下，每个串前缀最大值个数都 \(-1\) ，仍然合法，一直做下去最多一个串后面有“新的”。
先把 \(S_i\) 贪心地赋为 \(0\) ，先讨论 \(A\) 后面只有旧的最大值，我们根据结论列一个等式：
记 \(A\) 此时已经有 \(cnt_A\) 个前缀最大值， \(B\) 此时有 \(cnt_B\) 个，\([i+1,n]\) 中有 \(P\) 的 \(cnt[i+1]\) 个前缀最大值，\(B\) 分了 \(k\) 个“旧的”和 \(m\) 个“新的”，那么
\[\begin{align} cnt_A+cnt[i+1]-k &=cnt_B+k+m \notag\\ cnt_A-cnt_B+cnt[i+1] &=2k+m \notag \end{align} \]发现左边此时已经是个定值，考虑右边等价的意义：选一个接在当前 \(B\) 的后面的 \(P\) 的上升子序列，“旧的”贡献为 \(2\) 、“新的”贡献为 \(1\) ，总贡献为 \(cnt_A-cnt_B+cnt[i+1]\)。
为什么？ 可能这很显然，但我就是卡死胡同了 贡献那里显然没问题，为什么能保证一定存在一个方案使 \(A\) 的后面只有“旧的”产生贡献？因为“新的”在 \(P\) 中一定存在一个前面的数比它大，我们先把要提出放在 \(B\) 后面的数提取出来，对于剩下的“旧的”前缀最大值都给 \(A\) ，对于没被选走的数， \(P\) 中在它前面且比它大的数在哪就把它丢哪去，这样就符合条件。
然后就考虑怎么找这个子序列了：若总贡献为 \(x\) 的能被找出来，那么 \(x-2\) 的也能被找出来（有 \(2\) 丢 \(2\) ，没 \(2\) 丢俩 \(1\) ) ，也就只要找到和为奇数、偶数的最大值。考虑 \(DP_{i,0/1}\) 表示以 \(P_i\) 为开头的、和为 偶数/奇数 的最大总和，转移就是 \(LIS\) 那样转移，\(DP_{i,op}=\max\limits_{j>i,P_j>P_i} DP_{j,op \otimes (val_i\&1)}+val_i\)，从后往前转移用个权值线段树就可以完成优化转移了。然后再从前往后去找最大值并删掉这个数的贡献，逐位贪心即可
对于此时 \(B\) 后面只有旧的最大值也是类似地推式子，不做赘述。
CODE
struct ST{
#define ls (u<<1)
#define rs ((u<<1)|1)
int mx[maxn<<2];
inline void pushup(int u){mx[u] = max(mx[ls],mx[rs]);}
void build(int u,int l,int r){
if(l == r) {mx[u] = -inf;return;}
int mid = (l+r)>>1;
build(ls,l,mid),build(rs,mid+1,r); pushup(u);
}
void modify(int u,int l,int r,int p,int val){
if(l == r) {mx[u] = val;return;}
int mid = (l+r)>>1;
(p <= mid) ? modify(ls,l,mid,p,val) : modify(rs,mid+1,r,p,val);
pushup(u);
}
int query(int u,int l,int r,int ql,int qr){
if(l >= ql && r <= qr) return mx[u];
int res = -inf,mid = (l+r)>>1;
if(ql <= mid) res = max(res,query(ls,l,mid,ql,qr));
if(mid < qr) res = max(res,query(rs,mid+1,r,ql,qr));
return res;
}
}odd,even;
inline bool check(int que,int dn){
int res; dn = max(dn,1);
if(que < 0) return 0; //NOTE!!!
res = (que&1) ? odd.query(1,1,n,dn,n) : even.query(1,1,n,dn,n);
//cout<= que);
}
int main(){
//freopen("cpp.in","r",stdin);
//freopen("cpp.out","w",stdout);
rd(n);
for(ri i = 1;i <= n;++i){
rd(p[i]);
if(p[i] < maxp) val[i] = 1;
else val[i] = 2,maxp = p[i];
//cout<= 1;--i){
int mx0 = even.query(1,1,n,p[i],n),mx1 = odd.query(1,1,n,p[i],n);
if(val[i] & 1) even.modify(1,1,n,p[i],mx1 + 1),odd.modify(1,1,n,p[i],mx0 + 1);
else even.modify(1,1,n,p[i],mx0 + 2),odd.modify(1,1,n,p[i],mx1 + 2);
cnt[i] = cnt[i+1] + val[i] - 1;
}
//for(ri i = 1;i <= n;++i) cout<maxa) + cnt[i+1] - cntb,maxb))
s[i] = '0',cnta += (p[i]>maxa),maxa = max(maxa,p[i]);
else if(check(cntb - cnta - (p[i]>maxa) + cnt[i+1],max(maxa,p[i])))
s[i] = '0',cnta += (p[i]>maxa),maxa = max(maxa,p[i]);
else s[i] = '1',cntb += (p[i]>maxb),maxb = max(maxb,p[i]);
}
if(cnta != cntb) puts("-1");
else puts(s + 1);
return 0;
}
总结
抄自上面博客
- 在做物品权值的时候，如果有性质如果 \(x\) 可以，那么 \(x-a\) 也可以，就可以考虑求出 \(b\mod a = i\) 的最大/最小值来优化。有的时候需要跑最短路（其实就是同余最短路，也告诉我们某些背包问题也可以用这个东西优化）
- 这个题一开始 \(A,B\) 原值新值都有，我们注意到原值不管在哪里都是前缀最大值，所以我们要考虑能否调整让问题变得简单。