The 15th Chinese Northeast Collegiate Programming Contest D. Lowbit(快速稳定区间修改)

D. Lowbit

原题链接

The 15th Chinese Northeast Collegiate Programming Contest D. Lowbit(快速稳定区间修改)
这题我们会想,加到一定次数以后会不会变成正常的区间操作呢,就类似于区间开根一样。然后我们发现确实如此,一个数加到一定次数之后实际上其二进制就只剩一个 1 1 1 了,后期就是不断乘 2 2 2 ,和区间开根类似处理一下就可以在一定次数之后变成区间乘的操作。

那么为什么操作少量次数以后其二进制就会变成只剩下一个 1 1 1 呢?我们考虑,对于一次操作,其二进制表示中 1 1 1 的总个数的变化。我们知道,加上 l o w b i t lowbit lowbit 是必定进位的,那么进位的话最终进位结束的地方肯定会多一个 1 1 1 ,那么我们就具体看进了多少位,只要连续进了 2 2 2 以上,那么其二进制中 1 1 1 的个数必定减少。那么只连续进 1 1 1 位的时候二进制中 1 1 1 的个数才会不变,我们考虑这是个什么情况,实际上就是倒数第一个 1 1 1 和倒数第二个 1 1 1 之间并不相邻,那么加上 l o w b i t lowbit lowbit 之后他们就会不断靠近,然后相邻,然后必然变成连续进位,然后必然 1 1 1 的个数减少。也就是说,如果其二进制中有两个 1 1 1 以上,在 [ 0 , x ] [0,x] [0,x] ( x x x 很小, x x x 是二进制中相邻两个 1 1 1 的最大距离,也就大概最多就是 l o g ( 2 e 5 ) log(2e5) log(2e5) )次操作之后,二进制中的 1 1 1 的个数必然减少,但又不可能减少到 0 0 0 ,也就是在少量操作之后,二进制位中 1 1 1 的个数必然变成 1 1 1 ,这样若干次操作之后就变成了区间乘法,我们就可以用类似区间开根的做法去解决。

#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));
            }
        }
    }
}
上一篇:SDUT 2021 Autumn Team Contest 4th


下一篇:2019-2020 ACM-ICPC Brazil Subregional Programming Contest