Close numbers#457
Solution
General Idea: We need to maintain a dynamic set of integers and efficiently find the minimal distance between any two closest elements. To achieve this:
Use a set to store all elements in sorted order. This allows insertion, deletion, and neighbor queries in (O(n)).
Use a multiset to store all pairwise differences between consecutive elements. This allows querying the minimal distance in (O(1)).
How operations are handled:
ADD x:
If (x) is new, insert it into the set.
Update the multiset of differences:
Add differences between (x) and its neighbors.
Remove the difference between the two neighbors that (x) now splits.
DEL x:
Remove (x) from the set.
Update the multiset of differences:
Remove differences between (x) and its neighbors.
Add difference between the two neighbors of (x) that are now adjacent.
FIND:
Simply return the smallest value in the multiset of differences.
All operations work in (O(n)) time, which is efficient for (N 10^5).
—
#include <bits/stdc++.h>
#define ld long double
#define nl "\n"
#define ull unsigned long long
#define rv return void
#define str string
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define vec vector
#define fixed(n) fixed << setprecision(n)
#define Moageza ios::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL);
using namespace std;
//////////////////////////////////////////////////////
void solve(){
int q;cin>>q;
multiset<int>ans;
set<int>st;
while(q--){
str s;cin>>s;
if(s=="ADD"){
int x;cin>>x;
if(!st.count(x)){
st.insert(x);
int f=0,ff=0;
auto it=st.upper_bound(x);
if(it!=st.end()){
f=*it;
ans.insert(*it-x);
}
it=st.lower_bound(x);
if(it!=st.begin()){
it--;
ff=*it;
ans.insert(x-*it);
}
if(f&&ff)ans.erase(ans.find(f-ff));
}
}else if(s=="FIND"){
cout<<*ans.begin()<<nl;
}else if(s=="DEL"){
int x;cin>>x;
if(st.count(x)){
int f=0,ff=0;
auto it=st.upper_bound(x);
if(it!=st.end()){
f=*it;
ans.erase(ans.find(*it-x));
}
it=st.lower_bound(x);
if(it!=st.begin()){
it--;
ff=*it;
ans.erase(ans.find(x-*it));
}
if(f&&ff)ans.insert(f-ff);
st.erase(x);
}
}
}
}
//////////////////////////////////////////////////////
signed main()
{
Moageza
int t = 1;
// cin >> t;
while (t--) {
solve();
// cout << nl;
}
return 0;
}