#1811. 崩坏天际线

    ID: 1811 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1439来源:qoj.ac数据:公开样例数学

崩坏天际线

崩坏天际线

题目描述

标题: 崩坏天际线 - Problem - QOJ.ac

#7872. 崩坏天际线

Statistics

The problem was used in the following contests:

题目背景

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。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 3
1 1 3
1 2 3
2 2
2