本文主要是介绍“红旗杯”第十五届东北地区大学生程序设计竞赛 D - Lowbit (gym-103145-D)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
一开始看官方题解没看懂 看了一波大佬的题解…
链接
（线段树 + 思维）
本题是给出两种操作 一种是 给出一个区间，将区间内的数字都加上自身的lowbit 另一种是求出区间总和 如果暴力单点修改每个点加上自身lowbit肯定是会TLE，我们需要去进行区间修改
我们可以发现所有2的n次方加上自身的lowbit都可以用乘2（左移1位）来达到
2 = 10B 4 = 100B 8 = 1000B 16 = 10000B
而且所有的非2的n次方加上自身的lowbit就是将最右边的1左移1位，那么根据题目中的数据范围是1e9 = 2的30次方，也就是最大情况下会以101010101的形式存在，最多移动15次后就变成了2的n次方，就可以用乘2的方法来实现了
如果当前区间内有不是2的n次方的就一直向下进行暴力单点修改，反正单点最多需要修改15次就可以变成2的n次方
最后如果当前区间内全部都是2的n次方，那么我们就可以利用lazy存需要乘几次2进行区间修改就可以了
需要用一个数组来记录是否当前区间内全部数都是2的n次方
如果一个数不是2的n次方那么需要注意在成为2的n次方前不可以取模 取模会影响答案
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;#define ll long long const int M = 100010;
const ll MOD = 998244353;ll num[M];ll tree[M << 2], lazy[M << 2];
// jg用来判断当前区间是否全部都是2的n次方
bool jg[M << 2];ll lowbit(ll x) {return x & (-x);}void pushup(int rt) {if (jg[rt << 1] && jg[rt << 1 | 1]) jg[rt] = true;tree[rt] = tree[rt << 1] + tree[rt << 1 | 1];tree[rt] %= MOD;}
void build(int rt, int l, int r) {jg[rt] = false;lazy[rt] = 1;if (l == r) {tree[rt] = num[l];// 如果tree[rt] == lowbit(tree[rt])则说明是2的n次方if (tree[rt] == lowbit(tree[rt])) jg[rt] = true;return;}int mid = (l + r) >> 1;build(rt << 1, l, mid);build(rt << 1 | 1, mid + 1, r);pushup(rt);
}void pushdown(int rt) {if (lazy[rt] > 1) {tree[rt << 1] *= lazy[rt];tree[rt << 1] %= MOD;tree[rt << 1 | 1] *= lazy[rt];tree[rt << 1 | 1] %= MOD;lazy[rt << 1] *= lazy[rt];lazy[rt << 1] %= MOD;lazy[rt << 1 | 1] *= lazy[rt];lazy[rt << 1 | 1] %= MOD;lazy[rt] = 1;}
}void update(int rt, int l, int r, int L, int R) {if (R < l || L > r) return;if (L >= l && R <= r && jg[rt]) {tree[rt] = tree[rt] << 1;tree[rt] %= MOD;lazy[rt] = lazy[rt] << 1;lazy[rt] %= MOD;return;}if (L >= l && R <= r && R == L) {tree[rt] += lowbit(tree[rt]);// 需要注意在成为2的n次方前不可以取模 取模会影响答案if (tree[rt] == lowbit(tree[rt])) {jg[rt] = true; tree[rt] %= MOD;}return;}int mid = (L + R) >> 1;pushdown(rt);update(rt << 1, l, r, L, mid);update(rt << 1 | 1, l, r, mid + 1, R);pushup(rt);
}ll query(int rt, int l, int r, int L, int R) {if (R < l || L > r) return 0;if (L >= l && R <= r) return tree[rt] % MOD;pushdown(rt);int mid = (L + R) >> 1;ll ans = 0;ans += query(rt << 1, l, r, L, mid);ans %= MOD;ans += query(rt <<1 | 1, l, r, mid + 1, R);ans %= MOD;return ans;
}int main() {int t;scanf("%d", &t);while (t--) {int n;scanf("%d", &n);for (int i = 1; i <= n; ++i) scanf("%lld", &num[i]);build(1, 1, n);int op, op1, l, r;scanf("%d", &op);while (op--) {scanf("%d", &op1);if (op1 == 1) {scanf("%d%d", &l, &r);update(1, l, r, 1, n);}else if (op1 == 2) {scanf("%d%d", &l, &r);printf("%lld\n", query(1, l, r, 1, n));}}}return 0;
}
这篇关于“红旗杯”第十五届东北地区大学生程序设计竞赛 D - Lowbit (gym-103145-D)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
