当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
6317：Segment
题目描述
ZY found a weird segment tree with range [1, n].
For one node [a, b] (a<b) we choose a random integer x in range [a, b), seperate the segment into [a,x] and [x+1,b].
While doing query on this segment tree, bad thing happens. For one query [l, r]. If we want to obtain the information of the range [l, r], what is the expected number of nodes in the segment tree that would be visited?
For example, when querying range [2,4] in this segment tree, we will visit nodes in red.
For one node [a, b] (a<b) we choose a random integer x in range [a, b), seperate the segment into [a,x] and [x+1,b].
While doing query on this segment tree, bad thing happens. For one query [l, r]. If we want to obtain the information of the range [l, r], what is the expected number of nodes in the segment tree that would be visited?
For example, when querying range [2,4] in this segment tree, we will visit nodes in red.
输入解释
The first line contains two integer n,q.
The following q lines each contain a query interval [l,r].
$1 \leq n,q \leq 10^6$.
The following q lines each contain a query interval [l,r].
$1 \leq n,q \leq 10^6$.
输出解释
For each query, output the expected number of visited nodes in a line, modulo 998244353.
输入样例
2 3 1 1 2 2 1 2
输出样例
2 2 1
来自杭电HDUOJ的附加信息
| Recommend | chendu |
最后修改于 2020-10-25T23:30:14+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 2000/1000MS(Java/Others) | 32768/32768K(Java/Others) |
登陆或注册以提交代码