#P17877. Growing Prefix Span

    ID: 16817 传统题 4000ms 512MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>动态规划多项式与生成函数FFT组合数学CF3000分治

Growing Prefix Span

题目描述

对于一个 1,2,…,n1,2,\ldots,n 的排列,令 sis_i 表示包含数值 1,2,…,i1,2,\ldots,i 的最短连续子数组的长度。

设 pos⁡(x)\operatorname{pos}(x) 为数值 xx 在排列中的位置,则

$$s_i=\max_{1\le x\le i}\operatorname{pos}(x)-\min_{1\le x\le i}\operatorname{pos}(x)+1.$$

对于每个 ii,给定区间约束 [li,ri][l_i,r_i]。请统计满足所有约束 li≤si≤ril_i\le s_i\le r_i 的排列数量,答案对 998244353998244353 取模。

输入格式

第一行包含整数 nn。

接下来 nn 行,第 ii 行包含两个整数 li,ril_i,r_i。

输出格式

输出一个整数,表示合法排列数量对 998244353998244353 取模后的结果。可能不存在合法排列,此时输出 00。

样例

3
1 1
2 2
3 3
4

合法排列为 (1,2,3)(1,2,3)、(2,1,3)(2,1,3)、(3,1,2)(3,1,2)、(3,2,1)(3,2,1)。

数据范围

1≤n≤2×1051\le n\le 2\times10^5,1≤li≤ri≤n1\le l_i\le r_i\le n。