# 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)); } } } }