题解：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;
}