A5722. 「ZJOI2019」线段树
编程题
省选/NOI-
知识点
题目描述
九条可怜是一个喜欢数据结构的女孩子，在常见的数据结构中，可怜最喜欢的就是线段树。
线段树的核心是懒标记，下面是一个带懒标记的线段树的伪代码，其中
<img width="800px" src="https://img.loj.ac.cn/2019/04/01/5ca213bd0a49e.png">
其中函数 $\texttt{Lson}(\text{Node})$ 表示 $\text{Node}$ 的左儿子，$\texttt{Rson}(\text{Node})$ 表示 $\text{Node}$ 的右儿子。
现在可怜手上有一棵 $[1, n]$ 上的线段树，编号为 $1$。这棵线段树上的所有节点的
- $1\ l\ r$，假设可怜当前手上有 $t$ 棵线段树，可怜会把每棵线段树复制两份（
- $2$，可怜定义一棵线段树的权值为它上面有多少个节点
线段树的核心是懒标记，下面是一个带懒标记的线段树的伪代码，其中
tag 数组为懒标记：<img width="800px" src="https://img.loj.ac.cn/2019/04/01/5ca213bd0a49e.png">
其中函数 $\texttt{Lson}(\text{Node})$ 表示 $\text{Node}$ 的左儿子，$\texttt{Rson}(\text{Node})$ 表示 $\text{Node}$ 的右儿子。
现在可怜手上有一棵 $[1, n]$ 上的线段树，编号为 $1$。这棵线段树上的所有节点的
tag 均为 $0$。接下来可怜进行了 $m$ 次操作，操作有两种：- $1\ l\ r$，假设可怜当前手上有 $t$ 棵线段树，可怜会把每棵线段树复制两份（
tag 数组也一起复制），原先编号为 $i$ 的线段树复制得到的两棵编号为 $2i − 1$ 与 $2i$，在复制结束后，可怜手上一共有 $2t$ 棵线段树。接着，可怜会对所有编号为奇数的线段树进行一次 $\texttt{Modify}(\text{root}, 1, n, l, r)$。- $2$，可怜定义一棵线段树的权值为它上面有多少个节点
tag 为 $1$。可怜想要知道她手上所有线段树的权值和是多少。输入格式
第一行输入两个整数 $n, m$ 表示初始区间长度和操作个数。
接下来 $m$ 行每行描述一个操作，输入保证 $1 \le l \le r \le n$。
接下来 $m$ 行每行描述一个操作，输入保证 $1 \le l \le r \le n$。
输出格式
对于每次询问，输出一行一个整数表示答案，答案可能很大，对 $998244353$ 取模后输出即可。
输入输出样例
输入 #1
5 5 2 1 1 3 2 1 3 5 2
输出 #1
0 1 6
说明/提示
|测试点|$n$|$m$|其他约定|
|:-:|:-:|:-:|:-:|
|$1$|$\le 10^3$|$\le 10$|无|
|$2$|$\le 10^3$|$\le 10$|无|
|$3$|$\le 10^3$|$\le 10^3$|无|
|$4$|$\le 10^3$|$\le 10^3$|无|
|$5$|$\le 10^5$|$\le 10^5$|询问只有一个|
|$6$|$\le 10^5$|$\le 10^5$|询问只有一个|
|$7$|$\le 10^5$|$\le 10^5$|询问只有一个|
|$8$|$\le 10^5$|$\le 10^5$|无|
|$9$|$\le 10^5$|$\le 10^5$|无|
|$10$|$\le 10^5$|$\le 10^5$|无|
对于 $100\%$ 的数据，$1 \le l \le r \le n$。
|:-:|:-:|:-:|:-:|
|$1$|$\le 10^3$|$\le 10$|无|
|$2$|$\le 10^3$|$\le 10$|无|
|$3$|$\le 10^3$|$\le 10^3$|无|
|$4$|$\le 10^3$|$\le 10^3$|无|
|$5$|$\le 10^5$|$\le 10^5$|询问只有一个|
|$6$|$\le 10^5$|$\le 10^5$|询问只有一个|
|$7$|$\le 10^5$|$\le 10^5$|询问只有一个|
|$8$|$\le 10^5$|$\le 10^5$|无|
|$9$|$\le 10^5$|$\le 10^5$|无|
|$10$|$\le 10^5$|$\le 10^5$|无|
对于 $100\%$ 的数据，$1 \le l \le r \le n$。