MENU

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
Last Modified: May 4, 2023
Archives Tip
QR Code for this page
Tipping QR Code