#1174. QOJ 43_5214

    ID: 1174 传统题 4000ms 512MiB 尝试: 1 已通过: 0 难度: 省选/NOI- 上传者: 标签>QOJ来源:qoj.ac 43_5214答案:本地AC标程生成树状数组模拟

QOJ 43_5214

QOJ 43_5214

题目描述

2 树状数组 2.1 题目描述 漆黑的晚上,九条可怜躺在床上辗转反侧。难以入眠的她想起了若干年前她的一次悲惨的 OI 比赛经历。那是一道基础的树状数组题。 给出一个长度为n 的数组A,初始值都为0,接下来进行m 次操作,操作有两种: • 1 x,表示将Ax 变成(Ax + 1) mod 2。 • 2 l r,表示询问(∑r i=l Ai) mod 2。 尽管那个时候的可怜非常的simple,但是她还是发现这题可以用树状数组做。当时非常 young 的她写了如下的算法: 1: function Add(x) 2: while x > 0 do 3: Ax ←(Ax + 1) mod 2 4: x ←x −lowbit(x) 5: end while 6: end function 7: 8: function Find(x) 9: if x == 0 then 10: return 0 11: end if 12: ans ←0 13: while x ≤n do 14: ans ←(ans + Ax) mod 2 15: x ←x + lowbit(x) 16: end while 17: return ans 18: end function 19: 20: function Query(l, r) 21: ansl ←Find(l −1) 22: ansr ←Find(r) 23: return (ansr −ansl + 2) mod 2 24: end function 其中lowbit(x) 表示数字x 最վ的非0 二进制位,例如lowbit(5) = 1, lowbit(12) = 4。进 行第一类操作的时候就调用Add(x),第二类操作的时候答案就是Query(l, r)。 如果你对树状数组比较熟悉,不难发现可怜把树状数组写错了:Add઼ Find 中x 变化 的方向反了。因此这个程序在最终测试时华丽的爆0 了。 然而奇怪的是,在当时,这个程序通过了出题人给出的大样例——这也是可怜没有进行对 拍的原因。 4

现在,可怜想要算一下,这个程序回答对每一个询问的概率是多少,这样她就可以再次的 感受到自己是一个多么非的人了。然而时间已经过去了很多年,即使是可怜也没有办法完全回 忆起当时的大样例。幸运的是,她回忆起了大部分内容,唯一遗忘的是每一次第一类操作的x 的值,因此她假定这次操作的x 是在[li, ri] 范围内等概率䲿ᵪ的。 具体来说,可怜给出了一个长度为n 的数组A,初始为0,接下来进行了m 次操作: • 1 l r,表示在区间[l, r] 中等概率选取一个x 并执行Add(x)。 • 2 l r,表示询问执行Query(l, r) 得到的结果是正确的概率是多少。 2.2 输入格式 第一行输入两个整数n, m。 接下来m 行每行描述一个操作,格式如题目中所示。 2.3 输出格式 对于每组询问,输出一个整数表示答案。如果答案化为最简分数后形如x y,那么你只需要 输出x × y−1 mod 998244353 后的值。(即输出答案模998244353)。 2.4 样例输入 5 5 1 3 3 2 3 5 2 4 5 1 1 3 2 2 5 2.5 样例输出 1 0 665496236 2.6 样例䀓䟺 在进行完Add(3) 之后,A 数组变成了[0, 1, 1, 0, 0]。所以前两次询问可怜的程序答案都是 1,因此第一次询问可怜一定正确,第二次询问可怜一定错误。 5

2.7 数据范围与约定 测试点编号 n m 其他约定 1 ≤5 ≤10 无 2 ≤50 ≤50 3 4 ≤3000 ≤3000 5 6 ≤105 ≤105 所有询问都在修改后 7 8 无 9 10 对于100% 的数据,保证1 ≤l ≤r ≤n。 6

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 10