5131. 火锅(困难)

单点时限: 2.0 sec

内存限制: 512 MB

请注意,本题与(简单)的差别仅在 $m$ 的范围上,其余内容一致。

你和你的队友换了一家评论区未被公关且好评如潮的火锅店吃火锅。

在涮菜的时候,你发现由于下锅时间不一致,而捞出锅时你不一定能捞到你下的菜(也有可能被你急急急的队友给捞走了),你既有可能吃到夹生的鸭肠,也有可能吃到煮久到嚼不动的鸭肠。

我们现在假定,$m$ 种菜品中,菜品 $i$ 需要花 $l_i$ 秒煮熟,而如果 $r_i$ 秒后还没有捞出锅就煮老了;只有在下锅后 $l_i$ 秒到 $r_i$ 秒内捞出的才是恰到好处的。

为了检查你们的涮菜操作是否是合理的,你记录下了完整的操作序列:

  • $\texttt{add }t_i$: 在第 $t_i$ 秒下锅了一份菜,这份菜是从 $m$ 种中均匀随机地选取的。
  • $\texttt{pop }t_i$: 在第 $t_i$ 秒从锅中均匀随机地捞起了一份菜。进行该项操作时,锅中一定还有菜品。

你想知道,期望下你能吃到多少份恰到好处的菜。

输入格式

输入第一行包含两个正整数 $m~(1 \leq m \leq 202\,305), n~(1 \leq n \leq 202\,305)$。

接下来 $m$ 行,每行两个整数 $l_i, r_i (1 \leq l_i \leq r_i \leq 202\,305)$,表示一种菜品的好区间。

接下来 $n$ 行,每行为以下两种中的一种:

  • $\texttt{add }t_i$
  • $\texttt{pop }t_i$

其中,$1 \leq t_i \leq 202\,305$,且 $t_i$ 互不相同,并且随着 $i$ 单调增。

输出格式

输出一行一个整数,表示期望下你能吃到恰到好处的菜的数量对 $998\,244\,353$ 取模的结果。

对答案取模的定义如下:可以证明,答案一定能表示成有理数 $p / q$,其中 $p, q$ 为一对互素的整数(特别地,$p$ 等于 $0$ 时 $q$ 为 $1$)。此时,你需要输出 $p \times q ^ {-1} \bmod 998\,244\,353$,可以证明这个答案唯一。

样例

Input
2 4
1 3
1 7
add 1
add 3
pop 5
pop 7
Output
748683266
Input
2 5
1 4
19 1919
add 1
pop 4
add 114
add 514
pop 1919
Output
1

6 人解决,8 人已尝试。

11 份提交通过,共有 20 份提交。

6.5 EMB 奖励。

创建: 1 年,4 月前.

修改: 1 年,4 月前.

最后提交: 11 月,4 周前.

来源: N/A

题目标签