QOJ.ac

QOJ

Time Limit: 8 s Memory Limit: 1024 MB Total points: 100
[+7]

# 7872. 崩坏天际线

Statistics

题目背景

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

题目描述

Q个事件依次发生。事件分为两种:

  • 1 l r ,表示一个新的区间[l,r]从天而降,满足1l<rn
  • 2 x,表示位置x发生崩坏,满足1xn,所有满足l<xx<r的区间[l,r]都会以12的概率变成[l,x],另12的概率变成[x,r]

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

输入格式

第一行两个整数 n,Q

接下来Q行每行表示一个事件,即1 l r2 x

输出格式

一行一个整数表示答案。

样例

输入 #1

3 3
1 1 3
1 2 3
2 2

输出 #1

2

样例解释

区间[1,3]发生崩坏,12概率变为[1,2]12概率变为[2,3],区间[2,3]未发生崩坏。

所以最后的期望长度之和为121+121+11=2

数据范围

对于所有数据:1n,Q500001l<rn1xn

Subtask 1 (10 pts): 1n,Q500

Subtask 2 (20 pts): 1n,Q5000,依赖Subtask 1

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

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