D. Lowbit

Original question link

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