Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:512 MB
统计

【题目描述】 有 n 个 xpp,他们的家在一条直线上,房子从左到右分别标号为 1 ∼ n。
过年了,这 n 个 xpp 要相(开)互拜(黑)年,xpp 觉得线下开黑比较有意思,所以 xpp 们会一起聚到某个 xpp 的家里,然后再开黑。 xpp 不是个非常随便的人, 所以在问及去哪个 xpp家开黑时,每个 xpp 都有自己的限制,具体来说,第 i 个 xpp 愿意去的房子必须位于 [li, ri] 中 (1 ≤ li ≤ i ≤ ri ≤ n),如果超出这个范围 xpp 就会因为太远而感到不悦。他们打算让你来指定去谁家,你指定的地方必须让每个 xpp 都愿意去,如果某个 xpp 不愿意去这个地方,那么你就会被 xpp A 掉。
你发现这就是最简单的区间求交问题,但事实上你还要应付一些别的事情。因为如果你指定了去某个人的家,这个人就会因为自己家被弄乱而感到愤怒,然后你就会被 xpp A 掉。于是你打算把这个锅推给 xpp,也就是说,你会挑选某些 xpp,使得这些 xpp 去他们中的任何一个人的家都满足限制。你想知道有多少个非空集合 S ,满足对于 S 中的所有 xpp 都愿意去 S 中的任何一个 xpp 家里。
形式化题意:给定数组 l, r ,求有多少个非空集合 S,满足 ∀i, j ∈ S, li ≤ j ≤ ri. 对 998244353 取模
【输入格式】
第一行一个整数 n,表示人数。
第二行 n 个整数,第 i 个整数为 li ,含义见题目描述。
第三行 n 个整数,第 i 个整数为 ri ,含义见题目描述。
【输出格式】
一个整数,表示答案,对 998244353 取模。

【样例 1 输入】
3
1 1 2 3 2 3 【样例 1 输出】 4 2 【样例 1 解释】 满足条件的集合有 {1}, {2}, {3}, {1, 2} 【样例 2 输入】 10 1 2 3 3 4 6 1 1 4 7 10 4 6 4 9 10 9 8 9 10 【样例 2 输出】 26

大样例下载
【数据范围与提示】
对于 100% 的数据,满足 1 ≤ n ≤ 200000, 1 ≤ li ≤ i ≤ ri ≤ n
【子任务】
• 子任务 1(10 pts):n ≤ 20。
• 子任务 2(20 pts):n ≤ 2000。
• 子任务 3(20 pts):ri-li ≤ 10。
• 子任务 4(20 pts):n ≤ 50000。
• 子任务 5(30 pts):没有额外限制。