「EZEC-11」Unmemorable

Luogu

IDLGP8180

Time1000ms

Memory128MB

DifficultyP6

O2优化洛谷月赛

Unputdownable 手中有一个长度为 $n$ 的排列 $a$。他在练习单调栈的时候用程序对于每一个 $i$ 求出了最大的 $l_i$ 使得 $a_{l_i} < a_i$ 且 $l_i<i$，以及最小的 $r_i$ 使得 $a_{r_i}<a_i$ 且 $r_i>i$。特别的，若这样的 $l_i$ 不存在，则定义为 $0$，不存在的 $r_i$ 则定义为 $n+1$。某日 Unputdownable 忘记了排列 $a$，而且只剩余**分别重排**后的 $l$ 和 $r$ 数组了，你能帮助他还原原来的排列 $a$ 吗？随后由于他发现无法还原 $a$，你只要告诉他有多少种可能的原排列 $a$。答案对于 $998244353$ 取模，数据保证至少存在一种方案。 ## Input 第一行输入一个整数 $n$。第二行输入 $n$ 个整数，表示重排后的 $l$。第三行输入 $n$ 个整数，表示重排后的 $r$。 ## Output 输出一行，包含一个整数，表示可能的排列数量对 $998244353$ 取模后的值。 [samples] ## Note **样例解释 1** 一种可能的排列是 $\{2,5,1,3,4\}$，$l$ 数组是 $\{0,1,0,3,4\}$，$r$ 数组是 $\{3,3,6,6,6\}$。 **本题采用捆绑测试。** - Subtask 1（5 pts）：$n\leq 8$。 - Subtask 2（15 pts）：$r_i\geq n$。 - Subtask 3（15 pts）：$n\leq 2000$，保证存在一个排列 $a$ 满足排列 $a$ 所求出的 $l,r$ 即为给定的。 - Subtask 4（25 pts）：$n\leq 10^6$，保证存在一个排列 $a$ 满足排列 $a$ 所求出的 $l,r$ 即为给定的。 - Subtask 5（40 pts）：无特殊限制。对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$0 \leq l_i,r_i \leq n+1$，**数据保证至少存在一种方案**。

Samples

Input #1

5
3 1 0 0 4
6 3 6 3 6

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「EZEC-11」Unmemorable",
    "description": {
      "content": "Unputdownable 手中有一个长度为 $n$ 的排列 $a$。 他在练习单调栈的时候用程序对于每一个 $i$ 求出了最大的 $l_i$ 使得 $a_{l_i} < a_i$ 且 $l_i<i$，以及最小的 $r_i$ 使得 $a_{r_i}<a_i$ 且 $r_i>i$。 特别的，若这样的 $l_i$ 不存在，则定义为 $0$，不存在的 $r_i$ 则定义为 $n+1$。 某日 Un",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8180"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Unputdownable 手中有一个长度为 $n$ 的排列 $a$。\n\n他在练习单调栈的时候用程序对于每一个 $i$ 求出了最大的 $l_i$ 使得 $a_{l_i} < a_i$ 且 $l_i<i$，以及最小的 $r_i$ 使得 $a_{r_i}<a_i$ 且 $r_i>i$。\n\n特别的，若这样的 $l_i$ 不存在，则定义为 $0$，不存在的 $r_i$ 则定义为 $n+1$。\n\n某日 Un...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments