自动搬运

查看原文

来自洛谷，原作者为

	墨笙_Mooos *　　　　　　　=.=*

搬运于2025-08-24 22:40:44，当前版本为作者最后更新于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;
}