题解：「Diligent-OI R3 B」天际线
ARIS2_0
·
·
题解
思路
我们尝试直接从左到右去钦定每个数。
首先无解是可以直接判的，无解当且仅当存在以下几种情况：
- 存在 $i,j$ 满足 $i<j,b_i=1,a_j=1$；
- 存在 $i$ 满足 $c_i=1$ 且 $a_i,b_i$ 有一个不为 $0$；
- $c_1=1$ 或 $c_n=1$。
都是可以简单证明的。
先考虑 $c_i=0$ 的情况。
由于我们要求字典序最小，那么肯定是尝试从小到大放数字，这在 $b_i=0$ 的地方没有问题，但是在 $b_i=1$ 的地方，由于其为后缀 $\max$，所以值是**当前没有放置的最大的数字**。你不能减小这个数字的值，因为你一旦减小，为了维护后缀 $\max$ 的性质，原来的值就要移动到更前面，这显然是不优的。
接下来考虑正解，令 $ans_i$ 为答案数组。
从左往右填数字时，每碰到一个 $c_i=1$ 的 $i$，我们都要保证它的前面和后面都有比它大的数。我们先考虑前面而不管后面的限制。
碰到 $c_i=1$ 的 $i$ 时，我们去看有没有 $j$ 满足 $j<i$ 且 $b_j=1$，如果有的话，$j$ 位置的值肯定大于 $i$ 位置的值，限制已经被解决，我们直接继续即可。
否则，前面位置填的数肯定满足 $ans_i=i$。我们肯定希望这个比我们大的数的位置离我们更近，以便最小化字典序。
如果 $c_{i-1}=0$，那么令 $ans_i=i-1$，$ans_{i-1}=i$ ，这样交换一下就是最优的。
否则，改动 $ans_{i-1}$ 的值可能又会牵扯到 $c_{i-1}=1$ 这个限制是否能满足，会比较麻烦。
不妨换个角度考虑，我们直接对于一个 $c_i=1$ 的连续段 $[l,r]$，一次性求出 $ans_{l-1},ans_l,\dots,ans_r$。根据前文所说，有 $i\in[1,l-2],ans_i=i$。
那么我们发现，由于需要满足 $ans_l<ans_{l-1},ans_{l+1}<\max(ans_{l-1},ans_l)=ans_{l-1},\dots$，一定有 $\max\limits_{i=l}^{r}ans_i<ans_{l-1}$，那么 $ans_{l-1}$ 的下界至少是 $r$。
既然这样，我们直接令 $ans_{l-1}=r$，$\forall i\in[l,r],ans_i=i-1$，即可得到最优构造。
最后是前面留的问题，我们为什么可以不管后面的限制。实际上是因为，由于 $c_n=0$，根据这个构造，$ans_n$ 一定大于所有 $b_i=0$ 的 $ans_i$，而 $c_i=1$ 的地方一定有 $b_i=0$，相当于保证了后面一定有一个比其大的数。
至此构造结束，时空复杂度均为 $O(n)$。
### Fun Fact
虽然题目非常脑电波但是主播并不是对脑电波做出来的，而是写了个 $O(n^3)$ 再用数据结构优化到 $O(n\log n)$，优化完了发现，模拟一下数据结构在干什么即可得到这个做法。
### Code
$c_i=1$ 连续段那个部分写难看了，仅供参考。
```cpp
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define fi first
#define se second
#define mp make_pair
#define debug1(x) cerr<<(#x)<<"="<<(x)<<" "
#define debug2(x) cerr<<(#x)<<"="<<(x)<<"\n"
template<class T>
inline void operator += (vector<T>&a,const T &b){a.emplace_back(b);}
namespace ARIS2_0{
constexpr int maxn=1e5+10;
bool a[maxn],b[maxn],c[maxn];
int pc[maxn],ctot=0;
int ans[maxn],bef[maxn];
void solve(){
int n;cin>>n;
ctot=0;
for(int i=1;i<=n;i++){
char ch;cin>>ch;
a[i]=(ch=='1');
}
for(int i=1;i<=n;i++){
char ch;cin>>ch;
b[i]=(ch=='1');
}
for(int i=1;i<=n;i++)bef[i]=0;
for(int i=1;i<=n;i++){
char ch;cin>>ch;
c[i]=(ch=='1');
bef[i]=(c[i-1]?bef[i-1]:i);
if(c[i])pc[++ctot]=i;
}
for(int i=1;i<=n;i++){
if(c[i] and (a[i] or b[i])){
cout<<"-1\n";
return;
}
}
int firb=0;
if(c[1] or c[n]){
cout<<"-1\n";
return;
}
for(int i=1;i<=n;i++){
if(b[i] and !firb){
firb=i;
}
if(firb and i>firb and a[i]){
cout<<"-1\n";
return;
}
}
for(int i=1;i<=n;i++)ans[i]=0;
int z1=1,z2=n;
bool maxmax=0;
for(int p=1;p<=ctot;p++){
for(int i=pc[p-1]+1;i<=pc[p]-2;i++){
if(b[i])ans[i]=z2--,maxmax=1;
else ans[i]=z1++;
}
if(pc[p-1]+1==pc[p]){
if(maxmax){
ans[pc[p]]=z1++;
continue;
}
ans[pc[p]]=z1++;
swap(ans[pc[p]],ans[bef[pc[p]]-1]);
continue;
}
if(b[pc[p]-1]){
ans[pc[p]-1]=z2--;
maxmax=1;
ans[pc[p]]=z1++;
}
else{
ans[pc[p]-1]=z1++,ans[pc[p]]=z1++;
if(!maxmax)swap(ans[pc[p]-1],ans[pc[p]]);
}
}
for(int i=pc[ctot]+1;i<=n;i++){
if(b[i])ans[i]=z2--;
else ans[i]=z1++;
}
for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
cout<<"\n";
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T=1;
cin>>T;
while(T--)ARIS2_0::solve();
return 0;
}
/*
g++ -std=c++14 -Wall -Wextra -Wshadow -Wconversion
*/
```