编程介的小学生
2018-12-03 06:24
采纳率: 92.7%
浏览 353
已采纳

一个二叉树的遍历方面的问题求问下各位大神了

Problem Description
ZY found a weird segment tree with range [1, n].
For one node 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.

Input
The first line contains two integer n,q.
The following q lines each contain a query interval [l,r].
1≤n,q≤106.

Output
For each query, output the expected number of visited nodes in a line, modulo 998244353.

Sample Input
2 3
1 1
2 2
1 2

Sample Output
2
2
1

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

相关推荐 更多相似问题