5484: Counting Stars
内存限制：128 MB
时间限制：15.000 S
评测方式：文本比较
命题人：
提交：5
解决：2
题目描述
As an elegant and accomplished girl, Bella loves watching stars at night (especially the Polaris). There are totally n stars in the sky. We can define ai as the initial brightness of i-th star.
At t-th second, the brightness of some stars may change due to stars' activity. To simplify this problem, we can approximately divide activities into two kinds:
1. ∀i∈[l,r] , the brightness of i-th star decreases by ai&(−ai)
2. ∀i∈[l,r],ai≠0 , the brightness of i-th star increases by 2k, where k satisfy 2k≤ai<2k+1
Also, Bella has some queries. For each query, she wants to know the sum of brightness of stars in the range [l,r], which means ∑ri=lai
As we all know, Bella is a big smart. Thus, she could not solve such difficult problem by herself. Please help her solve this problem and answer her queries.
Since the answer may be too large, please output the answer modulo 998244353
At t-th second, the brightness of some stars may change due to stars' activity. To simplify this problem, we can approximately divide activities into two kinds:
1. ∀i∈[l,r] , the brightness of i-th star decreases by ai&(−ai)
2. ∀i∈[l,r],ai≠0 , the brightness of i-th star increases by 2k, where k satisfy 2k≤ai<2k+1
Also, Bella has some queries. For each query, she wants to know the sum of brightness of stars in the range [l,r], which means ∑ri=lai
As we all know, Bella is a big smart. Thus, she could not solve such difficult problem by herself. Please help her solve this problem and answer her queries.
Since the answer may be too large, please output the answer modulo 998244353
输入
The first line contains an integer T(T≤5) , denoting the number of test cases.
For each test case:
The first line contains an integers n(1≤n≤100000), denoting the number of stars .
The second line contains n integers a1,a2,…,an(1≤ai≤109), denoting the initial brightness of stars.
The third line contains an integer q(1≤q≤100000), denoting the number of operations.
Each of the next q lines contains three integers opti,li,ri, denoting the kind of operations and ranges.
opti=1 means Bella's query.
opti=2 means the first kind of stars' activity.
opti=3 means the second kind of stars' activity.
It is guaranteed that for all test cases, ∑n≤4×105,∑q≤4×105.
For each test case:
The first line contains an integers n(1≤n≤100000), denoting the number of stars .
The second line contains n integers a1,a2,…,an(1≤ai≤109), denoting the initial brightness of stars.
The third line contains an integer q(1≤q≤100000), denoting the number of operations.
Each of the next q lines contains three integers opti,li,ri, denoting the kind of operations and ranges.
opti=1 means Bella's query.
opti=2 means the first kind of stars' activity.
opti=3 means the second kind of stars' activity.
It is guaranteed that for all test cases, ∑n≤4×105,∑q≤4×105.
输出
For each Bella's query, output the answer modulo 998244353 in a single line.
样例输入 复制
1
5
5 2 2 9 7
4
2 1 5
1 1 1
3 1 3
1 2 5
样例输出 复制
4
14