2021“MINIEYE杯”中国大学生算法设计超级联赛（8）线段树

Counting Stars
Time Limit: 8000/4000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1045 Accepted Submission(s): 338

Problem Description
As an elegant and accomplished girl, Bella loves watching stars at night (especially the Polaris). There are totally n stars in the sky. We can define ai as the initial brightness of i-th star.
At t-th second, the brightness of some stars may change due to stars' activity. To simplify this problem, we can approximately divide activities into two kinds:

?i∈[l,r] , the brightness of i-th star decreases by ai&(?ai)
?i∈[l,r],ai≠0 , the brightness of i-th star increases by 2k, where k satisfy 2k≤ai<2k+1

Also, Bella has some queries. For each query, she wants to know the sum of brightness of stars in the range [l,r], which means ∑ri=lai
As we all know, Bella is a big smart. Thus, she could not solve such difficult problem by herself. Please help her solve this problem and answer her queries.
Since the answer may be too large, please output the answer modulo 998244353
Input
The first line contains an integer T(T≤5) , denoting the number of test cases.
For each test case:
The first line contains an integers n(1≤n≤100000), denoting the number of stars .
The second line contains n integers a1,a2,…,an(1≤ai≤109), denoting the initial brightness of stars.
The third line contains an integer q(1≤q≤100000), denoting the number of operations.
Each of the next q lines contains three integers opti,li,ri, denoting the kind of operations and ranges.
opti=1 means Bella's query.
opti=2 means the first kind of stars' activity.
opti=3 means the second kind of stars' activity.
It is guaranteed that for all test cases, ∑n≤4×105,∑q≤4×105.
Output
For each Bella's query, output the answer modulo 998244353 in a single line.
Sample Input

155 2 2 9 742 1 51 1 13 1 31 2 5

Sample Output

414

Source
【2021“MINIEYE杯”中国大学生算法设计超级联赛（8）】2021“MINIEYE杯”中国大学生算法设计超级联赛（8）

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define x first #define y second #define lson now << 1 #define rson now << 1 | 1using namespace std; const int mod = 998244353; const int N = 100010; struct node { long long int sum, val; long long int lazy; } tree[N << 2]; long long int a[N]; int n, t, q, k, u, v; long long int p[N]; long long int up_num(int x) { for (int i = 31; i >= 0; i--) { if ((x >> i) & 1) { return p[i]; } } return 0; }long long int lowbit(long long int x) { return x & -x; }void pushup(int now) { tree[now].sum = (tree[lson].sum + tree[rson].sum) % mod; tree[now].val = (tree[lson].val + tree[rson].val) % mod; }void pushdown(int now, int l, int r) { if (tree[now].lazy) { tree[lson].lazy = (tree[lson].lazy + tree[now].lazy) % mod; tree[rson].lazy = (tree[rson].lazy + tree[now].lazy) % mod; tree[lson].val = p[tree[now].lazy] * (tree[lson].val % mod) % mod; tree[rson].val = p[tree[now].lazy] * (tree[rson].val % mod) % mod; tree[now].lazy = 0; } }void build(int now, int l, int r) { tree[now].lazy = 0; if (l == r) { long long int w = up_num(a[l]); tree[now].val = w % mod; tree[now].sum = (a[l] - w + mod) % mod; return; } int mid = (l + r) >> 1; build(lson, l, mid); build(rson, mid + 1, r); pushup(now); } long long int query(int now, int l, int r, int al, int ar) { if (al <= l && ar >= r) { return (tree[now].sum + tree[now].val) % mod; } pushdown(now, l, r); int mid = (l + r) >> 1; long long int res = 0; if (al > mid) { res = (res + query(rson, mid + 1, r, al, ar) % mod) % mod; } else if (ar <= mid) { res = (res + query(lson, l, mid, al, ar) % mod) % mod; } else { res = (res + query(rson, mid + 1, r, al, ar) % mod) % mod; res = (res + query(lson, l, mid, al, ar) % mod) % mod; } return res % mod; } void update1(int now, int l, int r, int al, int ar) { if (!tree[now].val) { return; } if (l == r) { long long int w = lowbit(tree[now].sum); if (w != 0) { tree[now].sum = (tree[now].sum - w + mod) % mod; } else { tree[now].val = 0; } return; } pushdown(now, l, r); int mid = (l + r) >> 1; if (al > mid) { update1(rson, mid + 1, r, al, ar); } else if (ar <= mid) { update1(lson, l, mid, al, ar); } else { update1(rson, mid + 1, r, al, ar); update1(lson, l, mid, al, ar); } pushup(now); } void update2(int now, int l, int r, int al, int ar) { if (!tree[now].val) { return; } if (al <= l && ar >= r) { tree[now].lazy = (tree[now].lazy + 1) % mod; tree[now].val = (tree[now].val + tree[now].val) % mod; return; } pushdown(now, l, r); int mid = (l + r) >> 1; if (al > mid) { update2(rson, mid + 1, r, al, ar); } else if (ar <= mid) { update2(lson, l, mid, al, ar); } else { update2(rson, mid + 1, r, al, ar); update2(lson, l, mid, al, ar); } pushup(now); }int main() { scanf("%d", &t); for (int i = 0; i < N; i++) { if (i == 0) { p[i] = 1; } else { p[i] = p[i - 1] * 2 % mod; } } while (t--) { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); } build(1, 1, n); scanf("%d", &q); while (q--) { scanf("%d %d %d", &k, &u, &v); if (k == 1) //查询 { printf("%lld\n", query(1, 1, n, u, v) % mod); } else if (k == 2) { update1(1, 1, n, u, v); } else { update2(1, 1, n, u, v); } } } return 0; }