Problem Description
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
Input
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.
Output
For each Bella's query, output the answer modulo 998244353 in a single line.
Sample Input
1
5
5 2 2 9 7
4
2 1 5
1 1 1
3 1 3
1 2 5
Sample Output
4
14
题意大致就是创建一种数据结构，需要支持查询区间和、区间删除lowbit、区间最高位左移1位这三种操作。线段树恰好适合区间求和等操作，考虑怎么对其进行改进。首先对于区间删除lowbit，线段树并没有办法针对求区间lowbit设置lazy tag，但注意到lowbit操作的本质，实际上就是将最右边一位的1删去，而输入保证每个数在int的范围内，故每个数至多只需要操作logn次即可变为0，因此对于区间删除lowbit可以考虑进行暴力删除，这样最坏复杂度也仅为(O(nlog^2n))，可以接受。而对于第三种操作即区间最高位左移1，直接维护貌似不是很方便，但是考虑到区间最高位左移一位相当于把最高位对应的那个数乘2，同时注意到查询操作实际上查询的是区间和，满足加法性质，这启发我们对于每一个ai，分开维护其最高位和除去最高位的剩下的部分，查询的时候把这两部分和加起来即可。
具体来说，我们建立一棵线段树，上面维护这么几部分内容：sum1（除去最高位对应的数的区间和），sum2（最高位对应的数的区间和）、flag（如果节点对应区间每个ai除了最高位以外均为0，那么flag为true）、tag2（对于区间最高位对应的数乘以2设置的懒标记，只累积乘2操作）。查询的时候直接输出区间对应的sum1 + sum2，对于区间修改需要写两个modify函数，modify1是对区间暴力删除lowbit，注意如果节点对应的flag为true，说明这个区间所有ai仅剩下最高位了，此时直接将区间的sum2置0即可。modify2则是对于sum2维护普通的区间乘（即题目说的最高位左移一位）。具体细节见代码注释。
#include <bits/stdc++.h>
#define mod 998244353
using namespace std;
//对于区间：查询和，每个数删掉最低的1，增加最高位的1（最高位的1往左移动一个位置）
//注意ai可以无穷大
long long lowbit(long long x) {
return x & (-x);
}
struct SegmentTree {
int l, r;
long long sum1, sum2;//真实的后半部分数值，后部分区间和 最高位区间和
bool flag;//区间内的低位值是否都为0，是的话flag = true
long long tag2;//对最高位操作的tag 只设计乘 不涉及加
} t[800005];
int n, q;
long long lo[100005], hi[100005];
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
t[p].flag = 0;//不要忘记！一定要清除全0标记
t[p].tag2 = 1;
if(l == r) {
t[p].sum1 = lo[l];//在这里不能模！！！
t[p].sum2 = hi[l];
if(!t[p].sum1) t[p].flag = 1;
return;
}
int mid = (l + r) >> 1;
build(2 * p, l, mid);
build(2 * p + 1, mid + 1, r);
t[p].sum1 = (t[2 * p].sum1 + t[2 * p + 1].sum1) % mod;
t[p].sum2 = (t[2 * p].sum2 + t[2 * p + 1].sum2) % mod;
t[p].flag = t[2 * p].flag & t[2 * p + 1].flag;
}
void spread(int p) {//下传延迟标记，针对修改最高位的操作
t[2 * p].tag2 = t[2 * p].tag2 * t[p].tag2 % mod;
t[2 * p + 1].tag2 = t[2 * p + 1].tag2 * t[p].tag2 % mod;
t[2 * p].sum2 = t[2 * p].sum2 * t[p].tag2 % mod;
t[2 * p + 1].sum2 = t[2 * p + 1].sum2 * t[p].tag2 % mod;
t[p].tag2 = 1;
}
void modify2(int, int, int, int);
void modify1(int p, int L, int R) {//针对减去lowbit的modify操作，直接暴力修改
if(t[p].l == t[p].r) {
if(!t[p].sum1) {
t[p].sum2 = 0;
t[p].flag = 1;
return;
}
t[p].sum1 -= lowbit(t[p].sum1);//下面这句不删掉就wa，虽然我也不知道为什么
//if(!t[p].sum1) t[p].flag = 1;
return;
}
if(t[p].flag) {//当前区间内所有低位值都是0，直接调用modify2函数修改高位
t[p].sum1 = t[p].sum2 = 0;
t[p].tag2 = 1;
return;
}
spread(p);
int mid = (t[p].l + t[p].r) >> 1;
if(L <= mid ) modify1(2 * p, L, R);
if(R > mid) modify1(2 * p + 1, L, R);
t[p].sum1 = (t[2 * p].sum1 + t[2 * p + 1].sum1) % mod;
t[p].sum2 = (t[2 * p].sum2 + t[2 * p + 1].sum2) % mod;//这个也要修改，因为有可能涉及到最高位
t[p].flag = t[2 * p].flag & t[2 * p + 1].flag;
}
void modify2(int p, int L, int R, int v) {
if(t[p].l >= L && t[p].r <= R) {
t[p].sum2 = t[p].sum2 * 2 % mod;
t[p].tag2 = t[p].tag2 * 2 % mod;
return;
}
spread(p);
int mid = (t[p].l + t[p].r) >> 1;
if(L <= mid) modify2(2 * p, L, R, v);
if(R > mid) modify2(2 * p + 1, L, R, v);
t[p].sum1 = (t[2 * p].sum1 + t[2 * p + 1].sum1) % mod;
t[p].sum2 = (t[2 * p].sum2 + t[2 * p + 1].sum2) % mod;
t[p].flag = t[2 * p].flag & t[2 * p + 1].flag;
}
long long ask(int p, int L, int R) {
if(t[p].l >= L && t[p].r <= R) {
return (t[p].sum1 + t[p].sum2) % mod;
}
spread(p);
long long ret = 0;
int mid = (t[p].l + t[p].r) >> 1;
if(L <= mid) ret += ask(2 * p, L, R);
if(R > mid) ret = (ret + ask(2 * p + 1, L, R)) % mod;
return ret;
}
signed main() {
int t;
cin >> t;
while(t--) {
scanf("%d", &n);
for(int i = 1; i <= n; i++) {
long long a;
scanf("%lld", &a);
hi[i] = lo[i] = 0ll;
for(int j = 30; j >= 0; j--) {
if((1ll << j) <= a) {
hi[i] = (1ll << j);//注意不能写成1 << j
lo[i] = a & (~hi[i]);
break;
}
}
}
build(1, 1, n);
scanf("%d", &q);
for(int i = 1; i <= q; i++) {
int opt, l, r;
scanf("%d%d%d", &opt, &l, &r);
if(opt == 1) {
printf("%lld
", ask(1, l, r));
} else if(opt == 2) {
modify1(1, l, r);
} else {
modify2(1, l, r, 2);
}
}
}
return 0;
}