题解 CF1381B 【Unmerge】
cosmicAC
2020-07-22 18:09:56
有一个简单的DP，$f_{i,j,k}$（$k\in \{0,1\}$）表示考虑排列$a$由第$i$位开始的后缀中一共有$j$个放进第$0$个数列里，（另$2n+1-i-j$个放在第$1$个数列里），并且第$i$个数放在第$k$个数列里，是否可能有解。
转移就是枚举第$i$个数后方第一个和$a_i$不在同一个序列里的位置$x$，
$$f_{i,j,k}=f_{i,j,k} \vee f_{x,j-(1-k)(x-i),1-k}$$
此处必须要满足$a_x\gt \max_{j=i}^{x-1}a_j$才能先选$\{a_i\dots a_{x-1}\}$再选$a_x$，并且选择的$x$必须让两个序列的长度都不会超过$n$。暴力DP复杂度$O(n^3)$，会TLE on test 2。
考虑优化这个DP。~~直接用`std::bitset`三方过4000~~
发现$a_x\gt \max_{j=i}^{x-1}a_j$这个限制相当于一个单调栈，可以使用如下过程来维护所有合法的$x$：
- 弹栈，直到当前栈顶$\gt a_i$或者栈空了
- 用栈中的所有元素更新$f_{i,*,*}$
- 将$a_i$压入栈中
然而暴力更新复杂度还是错的。观察一下dp转移下标中的$j-(1-k)(x-i)$，发现所有的第二维坐标形成了一条竖直线（当$k=1$）或对角线（当$k=0$），所以对于每一列和每一条副对角线，维护此直线之内所有合法$x$对应的$f$值之和，就可以支持$O(1)$的插入/删除/查询此直线中是否有$1$了。复杂度$O(n^2)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int f[4010][2010][2],n,a[4010],T,sta[4010],vsm[2010],dsm[4010];
void ins(int x,int v){
for(int i=0;i<=n;i++)vsm[i]+=v*f[x][i][0];
for(int i=x;i<=2*n && i-x<=n;i++)dsm[i]+=v*f[x][i-x][1];
}
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=1;i<=2*n;i++){
scanf("%d",a+i);
for(int j=0;j<=n;j++)f[i][j][0]=f[i][j][1]=0;
}
for(int i=0;i<=n;i++)vsm[i]=0;
for(int i=0;i<=2*n;i++)dsm[i]=0;
for(int i=2*n,tp=0;i;i--){
if(i>n)f[i][2*n+1-i][0]=f[i][0][1]=1;
while(tp&&a[sta[tp]]<a[i])ins(sta[tp--],-1);
for(int j=max(n+1-i,0);j<=n&&j+i<=2*n+1;j++){
f[i][j][1]=vsm[j];
if(j+i<=2*n)f[i][j][0]=dsm[j+i];
}
sta[++tp]=i;ins(i,1);
}
puts(f[1][n][0]|f[1][n][1]?"YES":"NO");
}
return 0;
}
```