首先考虑固定一个无法辨认的位置集合$S$，我们该如何求出字典序最小的排列。

令$nex_i$表示$>i$的位置中第一个为$1$的位置，若不存在则为$n+1$。

• 对于$c_i=1$的位置$i$，他的限制是其$>[1,nex_i-1]$
• 对于$c_i=0$的位置$i$，他没有任何限制。

我们考虑将所有$c_i=1$的元素移动到第$nex_i$个元素的前面。后文都在移动后的排列上考虑。

现在，对于$c_i=1$的位置$i$，他的限制是其$>i$前面的所有元素；对于$c_i=0$的位置$i$，仍然没有限制。

我们从前到后依次确定每个无法辨认的位置填什么，填能填且符合要求的数中最小的那个。正确性显然。

$dp_{i,j}$表示考虑了位置$\le i$且权值$\le j$的元素，他们的方案数。

令$Max_{i}$表示$max\{a_1...a_i\}$，$pos_i$表示权值为$i$的元素所在的位置。

当$pos_j>i$时：$dp_{i,j}=dp_{i,j-1}$

当$c_{pos_j}=0$时：

• $pos_j$位置选择：$dp_{i,j-1}$
• $pos_j$位置不选择：我们需要位置$>pos_j$的权值$

当$c_{pos_j}=1$时： - $pos_j$位置选择：$dp_{i,j-1}$ - $pos_j$位置不选择：我们需要权值在$(Max_{pos_j-1},j)$的元素都选择，因此方案数为$dp_{i,Max_{pos_j-1}}$

至此，我们就有了一个$O(n^2)$的做法。

我们将转移方程列一下：

if(pos[j]>i)
    dp[i][j]=dp[i][j-1];
else if(typ[pos[j]]==1)
    dp[i][j]=dp[i][j-1]+dp[i][Max[pos[j]-1]];
else
    dp[i][j]=dp[i][j-1]+dp[pos[j]][j-1];

称第一种转移为“平凡转移”，第二、三种转移为“非平凡转移”。

考虑从小到大扫描$i$，每次会加进来一个非平凡转移。加进来的是$j=a_i$的转移。

我们考虑构建一张$n+1$个点的有向无环图，初始为$0,1,2,......,n$，$i->i+1$，$0$处权值为$1$。

$dp_{i,j}$就是目前这个有向无环图中所有点的权值$*$这个点到$j$的路径数之和。

如果$typ_i=0$，相当于将$a_i$位置的权值加上$dp_{i,a_{i}-1}$。

如果$typ_i=1$，相当于让$Max_{i-1}$与$a_i$连边。

观察到所有新连的边互不相交，因此任意两点$i,j$之间路径数量为$2^{edge_{i,j}}$，其中$edge_{i,j}$为完全包含在$i,j$两点之间的额外边数量。

现在这个问题可以用一颗线段树维护，每个节点维护权值$*2^{edge_{x,n}}$，需要支持区间乘，单点加，区间和。

代码：https://uoj.ac/submission/677924