题解：CF1732D1 Balance (Easy version)

原题链接

• 洛谷 CF1732D1 Balance (Easy version)

解题思路

考虑通过直接模拟来解决。维护一个 set，在每次插入操作 + 时，将元素插入集合中；在查询操作 * 时，从小到大暴力枚举 t 的值。

然而，这种方法在最坏情况下会导致时间复杂度为 $O(q^2)$。例如在前一半操作频繁插入 $1, 2, \dots, \frac{q}{2}$，而后一半的操作频繁查询 $1$ 时，无法满足题目时间限制。

考虑优化，注意到集合中的元素是单调递增的。因此，对于每个数 $x$ 的查询，答案只会增大而不会减小。我们可以利用 map 来记录每个数 $x$ 上一次查询的答案，若再次遇到相同的查询，则可以从上次的结果继续计算，而不必重新从头开始。

优化后的最坏情况是：前半部分的操作插入 $1, 2, \dots, \frac{q}{2}$，后半部分的操作查询 $1, 2, \dots, \frac{q}{2}$。此时，对于第 $i$ 个数，我们最多需要枚举约 $\frac{q/2}{i}$ 次，因此时间复杂度为 $O(\sum_{i=1}^{q/2}\frac{q/2}{i})=O(q \log q)$。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=200005;
set<ll> s;
map<ll,ll> m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int q;
	cin>>q;
	s.insert(0);
	while(q--)
	{
		char op;
		ll x;
		cin>>op>>x;
		if(op=='+')s.insert(x);
		else if(op=='?')
		{
			ll ans=m[x];
			while(s.find(ans)!=s.end())ans+=x;
			m[x]=ans;
			cout<<ans<<'\n';
		}
	}
	return 0;
}