E - Mex and Update Editorial by nok0
区間を set で管理するテクニックによる解法「区間を set で管理するテクニック」と俗に呼ばれている手法を用いることで簡単に解くことができます。
#include <bits/stdc++.h>
using namespace std;
template <class T>
struct range_set {
private:
const T TINF = std::numeric_limits<T>::max() / 2;
T sum;
std::set<std::pair<T, T>> st;
public:
range_set() : sum(0) {
st.emplace(-TINF, -TINF);
st.emplace(TINF, TINF);
}
//[l, r) is covered?
bool covered(const T l, const T r) {
assert(l <= r);
if(l == r) return true;
auto itr = prev(st.upper_bound({l, TINF}));
return itr->first <= l and r <= itr->second;
}
//[x, x + 1) is covered?
bool covered(const T x) { return covered(x, x + 1); }
// return section which covers[l, r)
// if not exists, return[-TINF, -TINF)
std::pair<T, T> covered_by(const T l, const T r) {
assert(l <= r);
if(l == r) return {-TINF, -TINF};
auto itr = prev(st.upper_bound({l, TINF}));
if(itr->first <= l and r <= itr->second) return *itr;
return {-TINF, -TINF};
}
// return section which covers[x, x + 1)
// if not exists, return[-TINF, -TINF)
std::pair<T, T> covered_by(const T x) { return covered_by(x, x + 1); }
// insert[l, r), and return increment
T insert(T l, T r) {
assert(l <= r);
if(l == r) return T(0);
auto itr = prev(st.upper_bound({l, TINF}));
if(itr->first <= l and r <= itr->second) return T(0);
T sum_erased = T(0);
if(itr->first <= l and l <= itr->second) {
l = itr->first;
sum_erased += itr->second - itr->first;
itr = st.erase(itr);
} else
itr = next(itr);
while(r > itr->second) {
sum_erased += itr->second - itr->first;
itr = st.erase(itr);
}
if(itr->first <= r) {
sum_erased += itr->second - itr->first;
r = itr->second;
st.erase(itr);
}
st.emplace(l, r);
sum += r - l - sum_erased;
return r - l - sum_erased;
}
// insert[x, x + 1), and return increment
T insert(const T x) { return insert(x, x + 1); }
// erase [l, r), and return decrement
T erase(const T l, const T r) {
assert(l <= r);
if(l == r) return T(0);
auto itr = prev(st.upper_bound({l, TINF}));
if(itr->first <= l and r <= itr->second) {
if(itr->first < l) st.emplace(itr->first, l);
if(r < itr->second) st.emplace(r, itr->second);
st.erase(itr);
sum -= r - l;
return r - l;
}
T ret = T(0);
if(itr->first <= l and l < itr->second) {
ret += itr->second - l;
if(itr->first < l) st.emplace(itr->first, l);
itr = st.erase(itr);
} else
itr = next(itr);
while(itr->second <= r) {
ret += itr->second - itr->first;
itr = st.erase(itr);
}
if(itr->first < r) {
ret += r - itr->first;
st.emplace(r, itr->second);
st.erase(itr);
}
sum -= ret;
return ret;
}
// erase [x, x + 1), and return decrement
T erase(const T x) { return erase(x, x + 1); }
int size() const { return (int)st.size() - 2; }
T mex(const T x = 0) const {
auto itr = prev(st.upper_bound({x, TINF}));
if(itr->first <= x and x < itr->second)
return itr->second;
else
return x;
}
T sum_all() const { return sum; }
std::set<std::pair<T, T>> get() const {
std::set<std::pair<T, T>> res;
for(auto &p : st) {
if(std::abs(p.first) == TINF) continue;
res.emplace(p.first, p.second);
}
return res;
}
void dump() const {
std::cout << "range_set:";
for(auto &p : st) {
if(std::abs(p.first) == TINF) continue;
std::cout << "[" << p.first << "," << p.second << "),";
}
std::cout << '\n';
}
};
int main() {
int n, q;
cin >> n >> q;
vector<int> a(n);
map<int, int> mp;
range_set<int> st;
for(auto &v : a) cin >> v, mp[v]++, st.insert(v);
while(q--) {
int i, x;
cin >> i >> x, --i;
if(!(--mp[a[i]])) st.erase(a[i]);
st.insert(a[i] = x);
mp[a[i]]++;
cout << st.mex() << endl;
}
}
posted:
last update: