Solution. LG3822 [NOI2017] 整数 / Trygub Numbers

Description

维护一个二进制数 $x$，支持两种操作：

• $x\gets x + a \cdot 2 ^ b$
• 询问 $x$ 第 $k$ 位的值

共 $n$ 次操作。

$1\le n\le 10^6,|a|\le10^9,0\le b,k\le30n$

Solution

常规做法是使用线段树，通过查询极长 0 / 1 连续段来维护进位借位，同时由于我们加减的是一个 $10^9$ 规模的数，直接做需要 $O(\log V)$ 次单点修改，总复杂度两只 $\log$，但注意到这 $\log V$ 次单点修改的位置是连续的，我们考虑暴力重构线段树上长度为 $O(\log V)$ 的段，然后做一次单点修改即可，这样复杂度为 $O(\log n + \log V)$。另外还需要压位。

所谓 Trygub Numbers 的思想是允许位上的值为负数，这样做的好处是，每当一位上的值发生进位，这个值都会从值域的一个端点回到值域中点，如果想要再发生一次进位，在该位上还需要进行至少进制数次加减法。这使得我们可以暴力维护进位，通过势能分析，令势能函数为所有位上值的绝对值之和，不难发现一次单点修改的复杂度是均摊 $O(1)$ 的。本题中一次加法可以拆分成 $O(\log V)$ 次单点修改，所以复杂度是均摊 $O(\log V)$ 的，压位就可以去掉这只 $\log$。

单点求值时我们取出目标位的值，并且找到比目标位低的最高的有值的位，如果该位值为负数，意味着需要发生一次借位，目标位实际值 $-1$。为了实现这里的操作，我们使用 map 维护所有有值的位，注意如果在修改过程中某一位变成了 $0$，需要及时将其从 map 中删去。

Code

namespace Main{
    const int base = 1 << 30;
    int n, t1, t2, t3;
    map<int, ll> dig;
    void add(int p, ll x){
        dig[p] += x;
        while(abs(dig[p]) >= base){
            dig[p + 1] += dig[p] / base;
            dig[p] %= base;
            if(dig[p] == 0) dig.erase(p);
            p++;
        }
        if(dig[p] == 0) dig.erase(p);
    }
    ll get(int p){
        auto iter = dig.lower_bound(p);
        ll res = iter == dig.end() || iter->first > p ? 0 : iter->second;
        if(iter != dig.begin() && prev(iter)->second < 0) res--;
        return (res + base) % base;
    }
    void Main(){
        input(n, t1, t2, t3);
        while(n--){
            int op;
            ll a, b;
            input(op);
            if(op == 1){
                input(a, b);
                add(b / 30, a * (1ll << (b % 30)));
            }
            else{
                input(a);
                write(get(a / 30) >> (a % 30) & 1);
                puts("");
            }
        }
        return;
    }
} // namespace

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。