Problem Statement
Lucida has a sequence of $n$ integers $a_1, a_2, \dots, a_n$. He asks you to perform two types of operations for him, which are described as follows:
1. 1 L R, add $lowbit(a_i)$ to each $a_i$ in the interval $[L, R]$.
2. 2 L R, query the sum of the numbers in the interval $[L, R]$.
$lowbit(x)$ is defined as the largest power of 2 that divides $x$. For example, lowbit(4)=4, lowbit(5)=1. Specially, lowbit(0)=0.
Lucida wants you to give the answer modulo $998244353$ for each of his queries.
This problem contains multiple test cases.
The first line contains a single integer $T$ ($1\leq T \leq 20$) indicating the number of test cases.
For each case, the first line contains an integer $n$ ($1 \leq n \leq 10^5$), the length of the sequence.
The next line contains $n$ integers $a_i$ ($1 \leq a_i < 998244353$) separated by spaces, representing the sequence.
The next line contains an integer $m$ ($1 \leq m \leq 10^5$), the number of operations.
The next $m$ lines, each line contains 3 integers $op, L, R$ ($1 \leq op \leq 2$, $1 \leq L \leq R \leq n$), represents one operation. The specific meaning is described above.
Output
For each query, output a line contains the answer modulo $998244353$.
Solving
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
#define ls(p) (p << 1)
#define rs(p) (p << 1 | 1)
//#define Single
const ll MOD = 998244353;
const int N = 1e5+1;
// 区间为二的幂直接乘2，否则直接暴力修改
bool check(int x) {return (x & (x - 1)) == 0;} // 判断是否为2的某次幂
int lowbit(int x) {return x & -x;}
struct SegTree
{
private:
struct Node
{
int l,r;
int lazymul; // 区间乘懒标记
int sum;
bool tag; // 是否为二的幂值区间
Node() : l(0),r(0),lazymul(1),sum(0),tag(false) {}
}tree[N<<2];
vector<int> arr;
void push_up(int p)
{
tree[p].sum = (tree[ls(p)].sum + tree[rs(p)].sum) % MOD;
tree[p].tag = tree[ls(p)].tag & tree[rs(p)].tag;
}
void apply_mul(int p,int val)
{
tree[p].sum = (tree[p].sum * val) % MOD;
tree[p].lazymul = (tree[p].lazymul * val) % MOD;
}
void push_down(int p)
{
if(tree[p].lazymul != 1)
{
apply_mul(ls(p),tree[p].lazymul);
apply_mul(rs(p),tree[p].lazymul);
tree[p].lazymul = 1;
}
}
public:
SegTree(const vector<int>& _arr) : arr(_arr)
{
build(1,1,(int)arr.size()-1);
}
void build(int p,int l,int r)
{
tree[p].l = l;
tree[p].r = r;
if(l == r)
{
tree[p].sum = arr[l];
tree[p].tag = check(arr[l]);
return;
}
int mid = (l + r) >> 1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void updateAdd(int p,int ul,int ur)
{
//如果该区间是二的幂区间，区间乘2修改
if(ul <= tree[p].l && tree[p].r <= ur && tree[p].tag)
{
tree[p].sum = (tree[p].sum * 2) % MOD;
tree[p].lazymul = (tree[p].lazymul * 2) % MOD;
// tree[p].tag = check(tree[p].sum);
// 不能加，区间和是二的次幂不代表每个元素都是二的次幂
return;
}
//否则暴力修改单个元素的值
if(tree[p].l == tree[p].r)
{
tree[p].sum += lowbit(tree[p].sum);
tree[p].tag = check(tree[p].sum);
return;
}
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
if(ul <= mid) updateAdd(ls(p),ul,ur);
if(mid < ur) updateAdd(rs(p),ul,ur);
push_up(p);
}
int querySum(int p,int ql,int qr)
{
if(ql <= tree[p].l && tree[p].r <= qr) return tree[p].sum % MOD;
push_down(p);
int mid = (tree[p].l + tree[p].r) >> 1;
int res = 0;
if(ql <= mid) res = (res + querySum(ls(p),ql,qr)) % MOD;
if(mid < qr) res = (res + querySum(rs(p),ql,qr)) % MOD;
return res;
}
};
|