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

区间修改）"/>

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

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 和倒数第二个 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)|1using 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(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(lson, l, mid, L, R);if (mid < R) update(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_JUDGEfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifint 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(1, 1, n, L, R);}else {printf("%d\n", query(1, 1, n, L, R));}}}
}