# D. Lowbit In this question, we wonder whether it will become a normal interval operation after adding a certain number of times, which is similar to interval root opening. Then we find that it is true that when a number is added to a certain number of times, there is actually only one binary 1 1 1. In the later stage, it is constant multiplication 2 2 2. Similar to interval root opening, it can become interval multiplication after a certain number of times.

So why is there only one binary after a small number of operations 1 1 What about 1? We consider that for an operation, its binary representation 1 1 Change in the total number of 1. We know, plus l o w b i t lowbit lowbit is bound to carry, so there must be one more place where the carry ends in the end 1 1 1. Then we will see how many digits we have entered, as long as we have entered continuously 2 2 2 or more, then its binary 1 1 The number of 1 must be reduced. Then only continuous 1 1 1 bit in binary 1 1 The number of 1 will remain unchanged. Let's consider what this is, which is actually the penultimate 1 1 1 and penultimate 1 1 1 is not adjacent, then add l o w b i t lowbit After lowbit, they will keep approaching, then adjacent, and then must become continuous carry, and then must 1 1 The number of 1 is reduced. That is, if there are two in its binary 1 1 Above 1, in [ 0 , x ] [0,x] [0,x] ( x x x is small, x x x is two adjacent binary 1 1 The maximum distance of 1, which is probably the most l o g ( 2 e 5 ) log(2e5) After log(2e5)) operations, the 1 1 The number of 1 is bound to decrease, but it is impossible to reduce to 0 0 0, that is, after a small number of operations, in the binary bit 1 1 The number of 1 must become 1 1 1. In this way, after several operations, it becomes interval multiplication, which can be solved by similar interval root opening method.

```#include <bits/stdc++.h>
#define lson rt<<1
#define rson (rt<<1)|1

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

const ll mod = 998244353;

int n, m;

ll tree[N << 3], lz[N << 3];
bool keep[N << 3];

void push_up(int rt) {
tree[rt] = (tree[lson] + tree[rson]) % mod;
keep[rt] = keep[lson] && keep[rson];
}

void push_down(int rt) {
if (lz[rt] == 1) return ;
lz[lson] = lz[lson] * lz[rt] % mod;
lz[rson] = lz[rson] * lz[rt] % mod;
tree[lson] = tree[lson] * lz[rt] % mod;
tree[rson] = tree[rson] * lz[rt] % mod;
lz[rt] = 1;
}

void build(int rt, int l, int r) {
keep[rt] = false;
lz[rt] = 1;
if (l == r) {
scanf("%lld", &tree[rt]);
return ;
}
int mid = l + r >> 1;
build(lson, l, mid);
build(rson, mid + 1, r);
push_up(rt);
}

void update_point(int rt, int l, int r, int L, int R) {
if (L <= l && r <= R && keep[rt]) {
tree[rt] = tree[rt] * 2 % mod;
lz[rt] = lz[rt] * 2 % mod;
return ;
}
if (l == r) {
ll pre = tree[rt];
tree[rt] += tree[rt] & (-tree[rt]);
if (tree[rt] == pre * 2) {
tree[rt] = tree[rt] % mod;
keep[rt] = true;
}
return ;
}
push_down(rt);
int mid = l + r >> 1;
if (mid >= L) update_point(lson, l, mid, L, R);
if (mid < R) update_point(rson, mid + 1, r, L, R);
push_up(rt);
}

int query(int rt, int l, int r, int L, int R) {
if (L <= l && r <= R) {
return tree[rt] % mod;
}
push_down(rt);
int mid = l + r >> 1, sum = 0;
if (mid >= L) sum = query(lson, l, mid, L, R) % mod;
if (mid < R) sum = (sum + query(rson, mid + 1, r, L, R)) % mod;
return sum;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
build(1, 1, n);
scanf("%d", &m);
while(m--) {
int op, L, R;
scanf("%d%d%d", &op, &L, &R);
if (op == 1) {
update_point(1, 1, n, L, R);
}
else {
printf("%d\n", query(1, 1, n, L, R));
}
}
}
}
```

Keywords: C Algorithm data structure

Added by mastercjb on Sun, 12 Sep 2021 03:33:04 +0300