题解 P8618 [蓝桥杯 2014 国 B] Log 大侠

墨笙_Mooos · 2022-10-25 07:04:50 · 题解

思路

注意到 \lfloor\log_2{a_i} + 1\rfloor = a_i 当且仅当 a_i \in \{1, 2\}。

若 a_i = 1 则无论怎样操作始终有 a_i = 1。

若 a_i > 1 则经过若干次操作后有 a_i = 2。考虑操作的次数，当 a_i = 2^{63} 时，只需要 4 次操作就有 a_i = 2，因此每个元素的操作次数是极少的，可以直接维护，当 a_i = 2 时删除 a_i 并不再维护。

由此，我们想到可以使用 map 对其实现删除元素和逐个修改。（都什么年代了还在写传统线段树、传统分块XD）

代码

具体实现上，可以维护整个数组的和，每次修改时减去其差值。

ll n, m, x, Ans;
__gnu_pbds::tree<ll, ll> Mp; // __gnu_pbds::tree 和 map 等效
decltype (Mp.begin ()) it, Lst; // 定义两个 iterator / 迭代器，作用类似于指针
int main ()
{
    std::cin.tie (nullptr), std::ios::sync_with_stdio (false);
    cin >> n >> m;
    For (i, 1, n)
    {
        cin >> x, Ans += x;
        if (x > 2) Mp.insert ({i, x});
    }
    For (i, 1, m)
    {
        static ll L, R; cin >> L >> R;
        it = Mp.lower_bound (L);
        while (it != Mp.end () && it->first <= R)
        {
            ll Log = log2l (it->second) + 1;
            Ans -= it->second - Log;
            Lst = it, it = next (it);
            if (Log == 2) Mp.erase (Lst);
            else Lst->second = Log;
        }
        cout << Ans << endl;
    }
    return 0;
}