HDU多校8 1004 Counting Stars（线段树）

Description

数据结构

1. 区间减去
2. 区间加上
3. 区间求和

Solution

难度比较适中的一道题，注意到操作1最多减去 次， 个数字需要的操作次数数量级为，考虑用线段树维护区间，可以 完成操作1，最终用一个 代表这个区别是不是全为 ，因为 就不需要再操作了。
对于操作2，每次只是对最高位进行修改，不妨将最高位和其他位分离开来维护，操作2就是对最高位做一次乘以2的操作，可以单点修改完成。

Code

/*
 * @Author: Kurisu
 */

#include<bits/stdc++.h>

const int N = 1e5 + 5;
const int mod = 998244353;

long long a[N], b[N];

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

namespace SegmentTree {
    struct node {
        int l, r;
        bool tag;
        long long sum1, sum2, lazy;
    }t[N << 2];
    void push_up(int rt) {
        t[rt].sum1 = (t[rt << 1].sum1 + t[rt << 1 | 1].sum1) % mod;
        t[rt].sum2 = (t[rt << 1].sum2 + t[rt << 1 | 1].sum2) % mod;
        t[rt].tag = (t[rt << 1].tag and t[rt << 1 | 1].tag);
    }
    void push_down(int rt) {
        if (t[rt].lazy) {
            t[rt << 1].lazy = t[rt << 1].lazy * t[rt].lazy % mod;
            t[rt << 1 | 1].lazy = t[rt << 1 | 1].lazy * t[rt].lazy % mod;
            t[rt << 1].sum1 = t[rt << 1].sum1 * t[rt].lazy % mod;
            t[rt << 1 | 1].sum1 = t[rt << 1 | 1].sum1 * t[rt].lazy % mod;
            t[rt].lazy = 1;
        }
        t[rt << 1].tag |= t[rt].tag;
        t[rt << 1 | 1].tag |= t[rt].tag;
        if (t[rt << 1].tag) {
            t[rt << 1].sum1 = t[rt << 1].sum2 = 0;
        }
        if (t[rt << 1 | 1].tag) {
            t[rt << 1 | 1].sum1 = t[rt << 1 | 1].sum2 = 0;
        }
    }
    void build(int rt, int l, int r) {
        t[rt].l = l, t[rt].r = r;
        t[rt].tag = 0;
        t[rt].lazy = 1;
        if (l == r) {
            t[rt].sum1 = a[l];
            t[rt].sum2 = b[l];    
            return ;
        }
        int mid = (l + r) >> 1;
        build(rt << 1, l, mid);
        build(rt << 1 | 1, mid + 1, r);
        push_up(rt);
    }
    long long query(int rt, int ql, int qr) {
        if (ql <= t[rt].l and qr >= t[rt].r) {
            return (t[rt].sum1 + t[rt].sum2) % mod;
        }
        push_down(rt);
        int mid = (t[rt].l + t[rt].r) >> 1;
        long long res = 0;
        if (ql <= mid) {
            res += query(rt << 1, ql, qr);
        }
        if (qr > mid) {
            res += query(rt << 1 | 1, ql, qr);
        }
        return res % mod;
    }
    void update_lowbit(int rt, int ql, int qr) {
        if (t[rt].tag) {
            return ;
        }
        if (t[rt].l == t[rt].r) {
            if (t[rt].sum2) {
                t[rt].sum2 -= lowbit(t[rt].sum2);
                return ;
            } else if (t[rt].sum1) {
                t[rt].sum1 = 0;
                t[rt].tag = 1;
                return ;
            } 
        }
        push_down(rt);
        int mid = (t[rt].l + t[rt].r) >> 1;
        if (ql <= mid) {
            update_lowbit(rt << 1, ql, qr);
        }
        if (qr > mid) {
            update_lowbit(rt << 1 | 1, ql, qr);
        }
        push_up(rt);
    }
    void update_bits(int rt, int ql, int qr) {
        if (ql <= t[rt].l and qr >= t[rt].r) {
            t[rt].sum1 = t[rt].sum1 * 2 % mod;
            t[rt].lazy = t[rt].lazy * 2 % mod;
            return ;
        }
        push_down(rt);
        int mid = (t[rt].l + t[rt].r) >> 1;
        if (ql <= mid) {
            update_bits(rt << 1, ql, qr);
        } 
        if (qr > mid) {
            update_bits(rt << 1 | 1, ql, qr);
        }
        push_up(rt);
    }
}

void solve() {
    int n, q; std::cin >> n;
    for (int i = 1; i <= n; i++) {
        int x; std::cin >> x;
        for (int j = 31; j >= 0; j--) {
            if ((1LL << j) <= x) {
                a[i] = (1LL << j);
                b[i] = x - a[i]; 
                break; 
            }
        }
    }
    SegmentTree::build(1, 1, n);
    std::cin >> q;
    while (q--) {
        int op, l, r; std::cin >> op >> l >> r;
        if (op == 1) {
            std::cout << SegmentTree::query(1, l, r) << '\n';
        } else if (op == 2) {
            SegmentTree::update_lowbit(1, l, r);
        } else if (op == 3) {
            SegmentTree::update_bits(1, l, r);
        }
    }
}

int main() {
    //freopen("data.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
    int T = 1; std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}