浙江龙网

  1. 首页 > 生活百科 > >

Div. 2 Codeforces Round #830 A-D( 二 )

生活百科


每个元素 \(i\) 只经过其倍数一次，共 \(\dfrac{n}{i}\) 次 。所有元素次数之和 \(O(\sum \dfrac{n}{i}) = O(n \log n)\)。
时间复杂度 \(O(q \log^2 q)\)
空间复杂度 \(O(q)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int q;cin >> q;set<ll> vis;map<ll, ll> last;while (q--) {char op;ll x;cin >> op >> x;if (op == '+') {vis.insert(x);}else {if (!last.count(x)) last[x] = x;while (vis.count(last[x])) last[x] += x;cout << last[x] << '\n';}}return 0;}D2题解知识点：STL ， 枚举 。
因为存在删除已存在元素的操作，这意味着我们之前得到的答案在未来可能不适用 。
因此需要对每个已询问过的数字维护一个已删除集合 map<ll,set<ll>> del，来得到目前某个元素的最大询问结果之前，是否有在序列中被删除的倍数 。
对于已删除集合的维护，需要对每个询问过程中遍历到的且存在于序列中的倍数维护一个影响列表 map<ll,vector<ll>> chg，来得到修改序列某个元素的状态时 ， 哪些询问过的元素的已删除集合会被修改 。
如此我们就维护了带删除求 mex 的数据结构 。
时间复杂度 \(O(q \log ^2 q)\)
空间复杂度 \(O(q\log q)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int q;cin >> q;set<ll> vis;//序列中存在的元素map<ll, ll> last;//某元素最大询问结果：记录需要维护的数据上界，超出最大询问结果的不需要考虑map<ll, set<ll>> del;//某元素的已删除集合：最大询问结果内，目前不存在于序列中的倍数map<ll, vector<ll>> chg;//某元素的影响列表：更改序列中某元素状态，已删除集合将发生变化的元素列表while (q--) {char op;ll x;cin >> op >> x;if (op == '+') {vis.insert(x);for (auto y : chg[x]) del[y].erase(x);//删除受x影响元素的已删除集合中的x，因为x已存在}else if (op == '-') {vis.erase(x);for (auto y : chg[x]) del[y].insert(x);//增加受x影响元素的已删除集合中的x，因为x已删除}else {if (!last.count(x)) last[x] = x;//新增已询问元素if (del[x].size()) cout << *del[x].begin() << '\n';//已删除集合存在元素 ， 优先使用else {//考虑最大询问结果是否可行，否则扩大最大询问结果while (vis.count(last[x])) {chg[last[x]].push_back(x);//已存在的x的倍数，在未来可能会被修改状态，影响x的结果last[x] += x;}cout << last[x] << '\n';}}}return 0;}

推荐阅读


上一篇：C# 7.0 添加和增强的功能【基础篇】

下一篇：Filter Spring中过滤器和拦截器(Interceptor)的区别和联系