#P12576. [集训队互测 2024day14]崩坏天际线

    ID: 11738 传统题 8000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3300分块数据结构单调栈数学概率DP树形DP线段树

[集训队互测 2024day14]崩坏天际线

题目背景

2079 年 1 月 4 日

我不知道该怎么办。

那些标记无处不在。

红色记号到处都是,各个街道无一例外。

失踪的人口每天都在增加。

事情变得愈发奇怪,越来越不真实。

我不知道自己还有多少时间。

王 国

题目描述

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

  • 11 ll rr ,表示一个新的区间[l,r][l,r]从天而降,满足1≤l<r≤n1 \le l < r \le n。
  • 22 xx,表示位置xx发生崩坏,满足1≤x≤n1 \le x \le n,所有满足l<xl<x且x<rx<r的区间[l,r][l,r]都会以12\frac{1}{2}的概率变成[l,x][l,x],另12\frac{1}{2}的概率变成[x,r][x,r]。

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

输入格式

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

接下来QQ行每行表示一个事件,即11 ll rr或22 xx。

输出格式

一行一个整数表示答案。

样例

输入 #1

3 3
1 1 3
1 2 3
2 2

输出 #1

2

样例解释

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

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

数据范围

对于所有数据:1≤n,Q≤500001 \le n,Q \le 50000,1≤l<r≤n1 \le l < r \le n,1≤x≤n1 \le x \le n。

SubtaskSubtask 11 (10(10 pts):pts): 1≤n,Q≤5001 \le n,Q \le 500。

SubtaskSubtask 22 (20(20 pts):pts): 1≤n,Q≤50001 \le n,Q \le 5000,依赖SubtaskSubtask 11。

SubtaskSubtask 33 (40(40 pts):pts): 保证所有事件11在所有事件22之前。

SubtaskSubtask 44 (30(30 pts):pts): 无特殊限制,依赖SubtaskSubtask 1,2,31,2,3。