2021“MINIEYE杯”中国大学生算法设计超级联赛（8）D.Counting Stars 线段树+二进制拆位+区间更新剪枝

😊 | Powered By HeartFireY

Problem Description

题目大意：给定一个序列，然后有三种操作：

1. o p = 1 op = 1 op=1，查询 [ l , r ] [l, r] [l,r]​区间和；
2. o p = 2 op = 2 op=2，将区间 [ l , r ] [l,r] [l,r]的每个数减去其 l o w b i t lowbit lowbit值，实际上就是将最低非 0 0 0位消去；
3. o p = 3 op = 3 op=3，将区间 [ l , r ] [l, r] [l,r]的每个数乘 2 k 2^k 2k，实际上就是将最高非 0 0 0​位左移一位。

显然是个线段树的应用题，但按照朴素方式进行维护显然复杂度是非常高的。我们来对这几个操作进行分析：

1. 区间求和，这个没啥花样，就是裸的线段树查询板子；

2. 区间数减 l o w b i t lowbit lowbit​值，不难发现对每个数字而言，最多执行 32 32 32​次减法操作后变成 0 0 0​。对于被消减为 0 0 0的区间，我们可以通过打标记将全零区间标识出来，这样可以避免每次更新的时候都暴力枚举到每个叶节点；

3. 区间数最高位左移，这个操作与 2 2 2​​操作相互独立，而且如果当前数字为 0 0 0​，该操作不会产生效果。因此上一个区间零标记仍然可以继续优化这个左移操作的更新过程。

   继续分析，由于最高位左移，只会对最高非 0 0 0​位产生影响，因此我们可以对每个数字进行拆位，即拆分位最高位和剩余位两个数字，分别进行维护。如此，对于第二个操作又需要进行修改：如果我们 u p d a t e update update某个节点，发现其剩余位为 0 0 0，那么表示进行一次减 l o w b i t lowbit lowbit操作后最高位也会变成零，我们需要手动将其置 0 0 0​，并打上零标记。

额外注意一点：在 p u s h d o w n pushdown pushdown操作中，我们的 l a z y lazy lazy标记是针对最高位的，不要把剩余位也给更新了…

Accepted Code

#include 
#define int long long
#define lson rt  1;
    update_1(lson, l, mid, L, R);
    update_1(rson, mid + 1, r, L, R);
    push_up(rt);
}

void update_2(int rt, int l, int r, int L, int R){
    if(L > r || R > l >> r;
        if(op == 1) cout