#XDS205. lowbit(x)

题目背景

在一次算法竞赛中,Oxy 遇到一个序列操作问题。他得到了一个长度为 nn 的正整数序列,需要支持两种操作:区间更新和区间查询。


题目描述

Oxy 得到了一段长度为 nn 的正整数序列 a1,a2,…,ana_1,a_2,\dots,a_n,他需要支持两种操作:

  • 1. 1 l r: 对于所有 l≤i≤rl \le i \le r,将 aia_i 增加 lowbit(ai)lowbit(a_i);
  • 2. 2 l r: 查询区间 [l,r][l,r] 内所有元素的和。

其中,lowbit(x)lowbit(x) 表示整数 xx 的二进制表示中最低位的 11 所对应的数值,即

lowbit(x)=x&(−x)lowbit(x) = x \& (-x)

特别规定:lowbit(0)=0lowbit(0)=0。
例如:lowbit(4)=4lowbit(4)=4,lowbit(5)=1lowbit(5)=1。

对于每次查询操作,你需要输出区间和对模数 998244353998244353 取模之后的结果。


输入格式

  • 第一行:一个整数 nn(1≤n≤1051 \le n \le 10^5),表示序列长度。
  • 第二行:nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n(1≤ai≤9982443521 \le a_i \le 998244352),表示初始序列。
  • 第三行:一个整数 qq(1≤q≤1051 \le q \le 10^5),表示操作次数。
  • 接下来 qq 行,每行三个整数 op,l,rop,l,r(1≤op≤2, 1≤l≤r≤n1 \le op \le 2,\ 1 \le l \le r \le n):
    • 若 op = 1:对区间 [l,r][l,r] 内的每个元素执行 ai←ai+lowbit(ai)a_i \leftarrow a_i + lowbit(a_i);
    • 若 op = 2:查询当前区间 [l,r][l,r] 内所有元素之和,并输出对 998244353998244353 取模的结果。

输出格式

对于每个查询(即每次 op = 2 的操作),输出一行一个整数,表示对应区间元素之和对 998244353998244353 取模后的结果。


数据范围

  • 1≤n≤1051 \le n \le 10^5
  • 1≤ai≤9982443521 \le a_i \le 998244352
  • 1≤q≤1051 \le q \le 10^5
  • 1≤op≤21 \le op \le 2
  • 1≤l≤r≤n1 \le l \le r \le n
Problem Info

#XDS205. lowbit(x)

ID 10038
类型 传统题
时间 1000ms
内存 256MiB
尝试 2 已通过 1
难度 4
上传者
标签
数据结构线段树lowbit