Codeforces Round #807 (Div. 2) E. Mark and Professor Koro 二进制/线段树

题目分析

模拟题目不难发现，实际上擦除操作就是在模拟二进制加法进位。那么可以得到原题意的转述：

将每个 a [ i ] a[i] a[i]看作 2 a [ i ] 2^{a[i]} 2a[i]，维护整个序列求和 ( ∑ i = 1 n 2 a [ i ] ) (\sum_{i = 1}^{n}2^{a[i]}) (∑i=1n​2a[i])和的最大位数，且要求支持带修。

考虑使用线段树维护二进制加法：

• 将每个叶节点视作二进制位，序列下标 1 1 1为最低位(感性理解)
• 维护加法操作：
  • 当加一个 2 x 2^x 2x时，检查第 x x x位是否为 1 1 1；
  • 如果 x x x位为 1 1 1，则需要维护进位操作，线段树上二分找到第一个非 1 1 1节点 p o s + 1 pos + 1 pos+1(或最后一个 1 1 1节点 p o s pos pos)，然后区间反转 [ x , p o s ] [x, pos] [x,pos]，修改 p o s + 1 pos + 1 pos+1为 1 1 1。
  • 如果 x x x位为 0 0 0，则直接单点加即可。
• 维护减法操作：
  • 当减一个 2 x 2^x 2x时，检查第 x x x位是否为 1 1 1；
  • 如果 x x x位为 1 1 1，可以直接减掉。
  • 如果 x x x位为 0 0 0，则需要维护借位操作，线段树二分找到最近的 1 1 1节点 p o s pos pos，并区间反转 [ x , p o s − 1 ] [x, pos - 1] [x,pos−1]，同时修改该位为 0 0 0
• 线段树维护区间和即可查询操作可以直接线段树上二分。

那么实现这两个操作即可。比较考察线段树的理解和引用。

Code

#include 
#define SEGRG 1, 1, 201000
#pragma gcc optimize(2)
#define int long long
#define endl '\n'
using namespace std;

const int N = 3e5 + 10;
int a[N], b[N];


namespace SegmentTree{
    #define ls rt  1;
        push_down(rt, r - l + 1);
        if(mid >= L) update_part(lson, L, R, val);
        if(mid > 1;
        push_down(rt, r - l + 1);
        if(mid >= pos) update_point(lson, pos, val);
        else update_point(rson, pos, val);
        push_up(rt);
    }

    static int query(int rt, int l, int r, int L, int R){
        if(l >= L && r > 1, ans = 0;
        push_down(rt, r - l + 1);
        if(mid >= L) ans += query(lson, L, R);
        if(mid > 1, ans = -1;
        if(tree[ls] && mid > pos) ans = get_first_one(lson, pos);
        if(tree[rs] && ans == -1) ans = get_first_one(rson, pos);
        return ans;
    }

    int get_last_one(int rt, int l, int r){
        if(l == r) return tree[rt] ? l : -1;
        push_down(rt, r - l + 1);
        int mid = l + r >> 1, ans = -1;
        if(tree[rs]) ans = get_last_one(rson);
        if(tree[ls] && ans == -1) ans = get_last_one(lson);
        return ans;
    }

    int get_first_zero(int rt, int l, int r, int pos){
        if(l == r) return !tree[rt] ? l : -1;
        push_down(rt, r - l + 1);
        int mid = l + r >> 1, ans = -1, lenl = mid - l + 1, lenr = r - mid;
        if(tree[ls]  pos) ans = get_first_zero(lson, pos);
        if(tree[rs] > n >> q;
    for(int i = 1; i > a[i];
    for(int i = 1; i > pos >> val;
        del(a[pos]), a[pos] = val, add(a[pos]);
        cout