崩坏天际线 - Problem

2079 年 1 月 4 日
我不知道该怎么办。
那些标记无处不在。
红色记号到处都是，各个街道无一例外。
失踪的人口每天都在增加。
事情变得愈发奇怪，越来越不真实。
我不知道自己还有多少时间。
王国

有$ Q $个事件依次发生。事件分为两种：

$ 1 $ $ l $ $ r $ ，表示一个新的区间$ [l,r] $从天而降，满足$ 1 \le l < r \le n $。
$ 2 $ $ x $，表示位置$ x $发生崩坏，满足$ 1 \le x \le n $，所有满足$ l<x $且$ x<r $的区间$ [l,r] $都会以$ \frac{1}{2} $的概率变成$ [l,x] $，另$ \frac{1}{2} $的概率变成$ [x,r] $。

请求出最后所有区间的期望长度之和，对$ 998244353 $取模。(区间$ [l,r] $的长度为 $ r-l $ )

第一行两个整数 $ n,Q $。

接下来$ Q $行每行表示一个事件，即$ 1 $ $ l $ $ r $或$ 2 $ $ x $。

一行一个整数表示答案。

区间$ [1,3] $发生崩坏，$ \frac{1}{2} $概率变为$ [1,2] $，$ \frac{1}{2} $概率变为$ [2,3] $，区间$ [2,3] $未发生崩坏。

所以最后的期望长度之和为$ \frac{1}{2}*1+\frac{1}{2}*1+1*1=2 $。

对于所有数据：$ 1 \le n,Q \le 50000 $，$ 1 \le l < r \le n $，$ 1 \le x \le n $。

$ Subtask $ $ 1 $ $ (10 $ $ pts): $ $ 1 \le n,Q \le 500 $。

$ Subtask $ $ 2 $ $ (20 $ $ pts): $ $ 1 \le n,Q \le 5000 $，依赖$ Subtask $ $ 1 $。

$ Subtask $ $ 3 $ $ (40 $ $ pts): $ 保证所有事件$ 1 $在所有事件$ 2 $之前。

$ Subtask $ $ 4 $ $ (30 $ $ pts): $ 无特殊限制，依赖$ Subtask $ $ 1,2,3 $。

QOJ.ac