【线段树】HDU 7116 Lowbit
2021-09-07 20:41:00 # ACM

题链

题目解析

区间对每个数加 $lowbit(a_i)$ ，区间求和；

由于对每个数加 $lowbit$ 的操作能很快使得一个数字在二进制下只剩最高位的 $1$，所以区间加 $lowbit$ 的操作做不了多少次，于是将每个数分为二进制下最高位的 $1$，以及其他位和；

对于区间加 $lowbit$ 操作暴力处理即可；

线段树维护节点信息：{
  区间最高位和；
  区间除最高位的和；
  区间除最高位剩下的和是否为 $0$；
}

如果区间除最高位剩下的和为 $0$，那么 $lowbit$ 操作时对于这个区间直接对最高位和 $*2$ 就可以了，否则递归到叶子节点将其暴力修改；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
    #define LL long long
    #define ULL unsigned long long
    #define Pair pair<LL ,LL >
    #define ls rt<<1
    #define rs rt<<1|1
    #define PI acos(-1.0)
    #define eps 1e-8
    #define mod 998244353
    #define MAXN 9e18
    #define MS 100005

// f[n] = 276601605(691504013^n - 308495997^n) (mod 1e9+9)

LL n,m,k;
struct node{
    LL high;
    LL low;
    LL la;
    LL ok;
}p[MS<<2];

LL lowbit(LL x){
    return x&(-x);
}

void push_up(int rt){
    p[rt].high = (p[ls].high + p[rs].high)%mod;
    p[rt].low  = (p[ls].low  + p[rs].low )%mod;
    p[rt].ok = p[ls].ok & p[rs].ok;
}

void push_down(int rt){
    if(p[rt].la != 1){
        p[ls].high *= p[rt].la;  p[ls].high %= mod;
        p[rs].high *= p[rt].la;  p[rs].high %= mod;
        p[ls].la   *= p[rt].la;  p[ls].la   %= mod;
        p[rs].la   *= p[rt].la;  p[rs].la   %= mod;
        p[rt].la = 1;
    }
}

void build(int l,int r,int rt){
    p[rt] = {0,0,1};
    if(l == r){
        LL x;
        cin >> x;
        while(x - lowbit(x)){
            p[rt].low += lowbit(x);
            x -= lowbit(x);
        }
        if(!p[rt].low) p[rt].ok = 1;
        p[rt].high = x;
        return;
    }
    int m = l+r>>1;
    build(l,m,ls);
    build(m+1,r,rs);
    push_up(rt);
}

void update(int L,int R,int l,int r,int rt){
    if(p[rt].ok && L <= l && r <= R){
        p[rt].high <<= 1;     p[rt].high %= mod;
        p[rt].la   <<= 1;     p[rt].la   %= mod;
        return;
    }
    if(l == r){
        if( p[rt].low + lowbit(p[rt].low) == p[rt].high ){
            p[rt].ok = 1;
            p[rt].low = 0;
            p[rt].high <<= 1;
            p[rt].high %= mod;
        }
        else{
            p[rt].low += lowbit(p[rt].low);
        }
        return;
    }
    int m = l+r>>1;
    push_down(rt);
    if(m >= L) update(L,R,l,m,ls);
    if(m <  R) update(L,R,m+1,r,rs);
    push_up(rt);
}

LL query(int L,int R,int l,int r,int rt){
    if(L <= l && r <= R){
        return (p[rt].high + p[rt].low)%mod;
    }
    int m = l+r>>1;
    push_down(rt);
    LL ans = 0;
    if(m >= L) ans = (ans + query(L,R,l,m,ls))%mod;
    if(m <  R) ans = (ans + query(L,R,m+1,r,rs))%mod;
    return ans%mod; 
}

void solve() {
    cin >> n;
    build(1,n,1);
    cin >> m;
    while(m--){
        int op,l,r;
        cin >> op >> l >> r;
        if(op == 1){
            update(l,r,1,n,1);
        }
        else if(op == 2){
            cout << query(l,r,1,n,1) << "\n";
        }
//        for(int i=1;i<=n;i++){
//            cout << i << " : " << query(i,i,1,n,1) << "\n";
//        }
//        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
//    srand(time(0));
    LL ce = 1;
    cin >> ce;
//    scanf("%lld",&ce);
    while(ce--) {
        solve();
    }

    return 0;
}
/*


*/
Prev
2021-09-07 20:41:00 # ACM
Next