题目背景
2079 年 1 月 4 日
我不知道该怎么办。
那些标记无处不在。
红色记号到处都是,各个街道无一例外。
失踪的人口每天都在增加。
事情变得愈发奇怪,越来越不真实。
我不知道自己还有多少时间。
王 国
题目描述
有Q个事件依次发生。事件分为两种:
- 1 l r ,表示一个新的区间[l,r]从天而降,满足1≤l<r≤n。
- 2 x,表示位置x发生崩坏,满足1≤x≤n,所有满足l<x且x<r的区间[l,r]都会以12的概率变成[l,x],另12的概率变成[x,r]。
请求出最后所有区间的期望长度之和,对998244353取模。(区间[l,r]的长度为 r−l )
输入格式
第一行两个整数 n,Q。
接下来Q行每行表示一个事件,即1 l r或2 x。
输出格式
一行一个整数表示答案。
样例
输入 #1
3 3 1 1 3 1 2 3 2 2
输出 #1
2
样例解释
区间[1,3]发生崩坏,12概率变为[1,2],12概率变为[2,3],区间[2,3]未发生崩坏。
所以最后的期望长度之和为12∗1+12∗1+1∗1=2。
数据范围
对于所有数据:1≤n,Q≤50000,1≤l<r≤n,1≤x≤n。
Subtask 1 (10 pts): 1≤n,Q≤500。
Subtask 2 (20 pts): 1≤n,Q≤5000,依赖Subtask 1。
Subtask 3 (40 pts): 保证所有事件1在所有事件2之前。
Subtask 4 (30 pts): 无特殊限制,依赖Subtask 1,2,3。