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;}

推薦閱讀