I am trying to solve this question for two days now.

Gist of the problem:

2D plane is given. Only the first quadrant is to be used. Three type of queries:

1. add x y: Add a point (x,y) to the coordinate system
2. remove x y: Remove an already existing point (x,y) from the coordinate system.
3. find x y: Find the left-most, bottom-most strictly above and on the right of (x,y).

Constraints: $$$1 \leq x,y \leq 1e9$$$ $$$queries \leq 2e5$$$

Approach to solution:

Firstly we need to map the $$$x$$$ co-ordinates to the 2e5 range, so that we can use a segment tree on them. I have done this using the code:

int n;cin>>n ;
f(i,0,n)
{
    cin>>type[i]>>queries[i][0]>>queries[i][1] ;
    v.push_back(queries[i][0]) ;
}
sort(v.begin(),v.end()) ;
int u = unique(v.begin(),v.end())-v.begin() ;
f(i,0,u) mp[v[i]] = i+1 ;

where v is a vector<int>, which saves the x coordinates for each query. Then we sort it, and use unique to find the unique entries. u is the total number of unique x coordinates. Then I use a map<int,int> mp, which stores the 1e9->2e5 mapping.

Now, we can build a segment tree. The segment tree will simply store the maximum y value for a segment. This is useful, as when find x y is called, we can query for the range (map[x]+1,u) for a number having value more than y. So, we get the mapped x.

Now we can store all the y's for a single (mapped) x,by creating an array of sets. I've used set<int> xset[MAXN] for this purpose. We can find the first element greater than some element by using xset[x].upper_bound(y).

All being said, here is the insertion function:

void insert(int node,int l,int r,int x,int y)
{
    if(x<l || r<x) return ;
    if(l==r)
    {
        tree[node] = {x,y} ;
        return ;
    }
    int mid = (l+r)>>1 ;
    insert(2*node+1,l,mid,x,y) ;
    insert(2*node+2,mid+1,r,x,y) ;
    tree[node].Y = max(tree[2*node+1].Y,tree[2*node+2].Y) ;
}

This is used along with the add x y query. tree represents the segment tree, where tree[i].X represents the x value and tree[i].Y represents the y value.

This function is called as:

if(type[i]=="add")
{
    xset[mp[queries[i][0]]].insert(queries[i][1]) ;
    insert(0,0,u,mp[queries[i][0]],queries[i][1]) ;
}

Now the removal function which goes along with the remove x y:

void remove(int node,int l,int r,int x,int y)
{
    if(x<l || r<x) return ;
    if(l==r)
    {
        tree[node] = {0,0} ;
        return ;
    }
    int mid = (l+r)>>1 ;
    remove(2*node+1,l,mid,x,y) ;
    remove(2*node+2,mid+1,r,x,y) ;
    tree[node].Y = max(tree[2*node+1].Y,tree[2*node+2].Y) ;
}

Which is called by the following code:

else if(type[i]=="remove")
{
    xset[mp[queries[i][0]]].erase(queries[i][1]) ;
    remove(0,0,u,mp[queries[i][0]],queries[i][1]) ;
}

And now comes the MVP. The function that goes along with the find x y:

int find_next(int node,int l,int r,int start,int end,int val)
{
    if(tree[node].Y<=val) 
        return 0 ;
    if(end<l || r<start) 
        return 0 ;
    if(l>r) 
        return 0;
    if(l==r)
    {
        return tree[node].X ;
    }
    int mid = (l+r)>>1 ;
    int v1 =  find_next(2*node+1,l,mid,start,end,val) ;
    if(v1==0)
        return find_next(2*node+2,mid+1,r,start,end,val) ;
    return v1 ;
    
}

Here have the range (start,end), where we need to find some element which has a value strictly greater than val. This is done by checking the maximum element of the current range. If it is greater than val, then we're sure we have come to the right place. If not, then we ignore this range by returning a zero.

Now we'd like to go to the left child if possible, because remember, in the find query, we needed the first element strictly greater than y. So, if possible, let's find such element in the left child. If no such element is found in the left child, then we look for the element with the mentioned properties in the right child.

Here is the main code that calls this code:

        else //find
        {
            int next = find_next(0,0,u,mp[queries[i][0]]+1,u,queries[i][1]) ;
            // int next = find_next2(0,0,u,mp[queries[i][0]],queries[i][1]) ;//<-----
            if(next==0) cout<<"-1\n"; 
            else
            {
                auto it = xset[next].upper_bound(queries[i][1]) ;//<----
                if(it==xset[next].end()) cout<<"-1\n" ;
                else 
                {
                    cout<<v[next-1]<<" "<<*it<<"\n" ;
                }
            }
        }

Here we try to find the next x element by calling find_next(0,0,u,mp[queries[i][0]]+1,u,queries[i][1]). Look that we're querying for the range mp[queries[i][0]]+1 to u, for values greater than queries[i][1]. If we get a zero as a result, then we know that no such element exists. If it's not a zero, then we can search our y in x's set. If it is not found then set.upper_bound returns an iterator pointing set.end(). So, we can check whether an element strictly greater than y is present in xset[next] or not. If it is present then we output the answer.

Remember f(i,0,u) mp[v[i]] = i+1 ;? This means that v's ith element is mapped as i+1th element. So, we o/p v[next]-1, instead of v[next].

Here is my latest submission. I've submitted ~10 similar solutions in 2 days. I know that I have got the most part of the solution right, but am not able to find what exactly am I doing wrong here.

Any help is appreciated.