The 15th Chinese Northeast Collegiate Programming Contest D. Lowbit

Northeast Collegiate Programming Contest D. Lowbit"/>

The 15th Chinese Northeast Collegiate Programming Contest D. Lowbit

The 15th Chinese Northeast Collegiate Programming Contest D. Lowbit
题目大意：
对于给定序列有两种操作
1 L R :修改区间[ L , R ]内的每个元素的值使其加上本身的lowbit值
2 L R :询问区间[ L , R ]的和
思路：
乍一看被难住在操作 1 上区间内每个元素都要加上其本身的lowbit值，这不是退化到单点修改了吗，单点修改必然超时
但通过lowbit性质可知

int lowbit(int x) {// x 的二进制表示中，最低位的 1 的位置。// lowbit(0b10110000) == 0b00010000//          ~~~^~~~~// lowbit(0b11100100) == 0b00000100//          ~~~~~^~~return x & -x;
}

当lowbit到某个数时可通过 *2 操作代替lowbit，即可进行区间的 *2 操作，设计乘法懒标记可以有效减低时间复杂度。

源码：解释和细节在源码中

#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;
template<class...Args>
void debug(Args... args) {//Parameter packauto tmp = { (cout << args << ' ', 0)... };cout << "\n";
}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>pll;
typedef pair<int, int>pii;
const ll N = 1e5 + 5;
const ll MOD = 998244353;
const ll INF = 0x7fffffff;
int lowbit(int num) {return num & -num;
}
bool check(int num) {//检查这个数是否可以通过 *2 代替lowbitreturn num == lowbit(num);
}
ll w[N];//存放权值
struct node {int l, r;//左右的范围ll sum;//总和bool flag;//是否可区间 *2ll cnt;//对于可直接乘的区间来说是所乘的数
} tree[N << 2];
void push_up(int root) {tree[root].sum = (tree[root << 1].sum + tree[root << 1 | 1].sum) % MOD;tree[root].flag = tree[root << 1].flag && tree[root << 1 | 1].flag;
}
void build(int root, int l, int r) {if (l == r)tree[root] = { l,r,w[r],check(w[r]),1 };else {tree[root] = { l,r,0,0,1 };//要赋初值int mid = l + r >> 1;build(root << 1, l, mid);build(root << 1 | 1, mid + 1, r);push_up(root);}
}
void push_down(int root) {auto& Root = tree[root], & left = tree[root << 1], & right = tree[root << 1 | 1];if (Roott>1) {//(x * a) * b = x * (a * b)leftt = (leftt * Roott) % MOD;left.sum = (left.sum * Roott) % MOD;rightt = (rightt * Roott) % MOD;right.sum = (right.sum * Roott) % MOD;Roott = 1;}
}
void modify(int root, int l, int r) {if (tree[root].l == tree[root].r) {//存在只能进行lowbit操作的数if (tree[root].flag) tree[root].sum = (tree[root].sum * 2) % MOD;else {//对于只能进行lowbit操作的数进行lowbit操作后再判断是否可以 *2 tree[root].sum = tree[root].sum + lowbit(tree[root].sum);//这个地方不能取模tree[root].flag = check(tree[root].sum);}return;}if (tree[root].l >= l && tree[root].r <= r) {if (tree[root].flag) {tree[root]t = (tree[root]t * 2) % MOD;tree[root].sum = (tree[root].sum * 2) % MOD;return;}}push_down(root);int mid = tree[root].l + tree[root].r >> 1;if (l <= mid)modify(root << 1, l, r);if (r > mid)modify(root << 1 | 1, l, r);push_up(root);
}
ll query(int root, int l, int r) {if (tree[root].l >= l && tree[root].r <= r) return tree[root].sum % MOD;push_down(root);int mid = tree[root].l + tree[root].r >> 1;if (r <= mid)return query(root << 1, l, r);else if (l > mid)return query(root << 1 | 1, l, r);else {ll left = query(root << 1, l, r);ll right = query(root << 1 | 1, l, r);ll ans;//push_upans = (left + right) % MOD;return ans;}
}
int main() {ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);int t;cin >> t;while (t--) {int n;cin >> n;for (int i = 1; i <= n; i++)cin >> w[i];build(1, 1, n);int m;cin >> m;for (int i = 0; i < m; i++) {int opt, l, r;cin >> opt >> l >> r;if (opt == 1)modify(1, l, r);else cout << query(1, l, r) << "\n";}}return 0;
}