博客

题目



题意:

维护一个集合。给定两种操作，1.插入一个集合中没有的数x；2.查找不在集合中的最小的k的倍数。


思路:

拿一个set维护集合中的数，另外拿map维护每个k上一次枚举到哪里，因为mex随着集合的增加只增不减的。这样复杂度也就n+n/2+n/3…≈nlnn


代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,m,k,T;
set<ll> sa;
map<ll,ll> mp;
void solve()
{
	char ch; ll x;
	cin>>ch>>x;
	if(ch=='+')
	{
		sa.insert(x);
	}
	else
	{
		for(ll i=mp[x]==0?x:mp[x];;i+=x)
		{
			if(!sa.count(i))
			{
				mp[x] = i;
				cout<<i<<"\n";
				return ;
			}
		}
	}
}
signed main(void)
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--)
	solve();
	return 0;
}