山东省第一届省赛 Ivan comes again

描述：

The Fairy Ivan gave Saya three problems to solve (Problem F). After Saya finished the first problem (Problem H), here comes the second.

This is the enhanced version of Problem H.

There is a large matrix whose row and column are less than or equal to 1000000000. And there are three operations for the matrix:

1.add: Mark an element in the matrix. The element wasn’t marked before it is marked.

2.remove: Delete an element’s mark. The element was marked before the element’s mark is deleted.

3.find: Show an element’s row and column, and return a marked element’s row and column, where the marked element’s row and column are larger than the showed element’s row and column respectively. If there are multiple solutions, return the element whose row is the smallest; and if there are still multiple solutions, return the element whose column is the smallest. If there is no solution, return -1.

Of course, Saya comes to you for help again.

输入：

The input consists of several test cases.

The first line of input in each test case contains one integer N (0<N≤200000), which represents the number of operations.

Each of the next N lines containing an operation, as described above.

The last case is followed by a line containing one zero.

输出：

For each case, print the case number (1, 2 …) first. Then, for each “find” operation, output the result. Your output format should imitate the sample output. Print a blank line after each test case.

题目大意就是有三种操作：添加，删除，查询，每次查询找出一个比他横纵坐标都大的元素点，优先横坐标最小的，其次是纵坐标最小；

这题就是一个STL set+pair 的应用

pair的功能是把两个值组合成一个值，set的功能是去重和排序，解决了重复元素的问题；

pair的用法：

pair<T1, T2> p1;//建立pair
p1.first;
p1.second//访问 p1的两个值

set简单用法

set<int>st;
st.begin()//返回开头元素 
st.insert()
st.end()
st.clear()
st.empty()
st.size()
st.count()//判断是否出现过
st.erase(key)//删除键值为key的元素
st.lower_bound()返回第一个大于等于key的定位器,注意返回的是定位器
st.upper_bound()返回第一个大于key的定位器,注意返回的是定位器

在本题中，添加用 insert ,删除用 erase ，查询用 lower_bound()即可

而且在set<pair<int,int>>中，排序规则恰好是优先第一个值大小排序，其次根据第二个值大小排序，完美的契合这个题；

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const ll maxx = 1e18;
const int N = 1e6+10;
const int pp = 1e4;
const double eps = 1e-8;
int n,cnt;
char s[10];
ll l,r;
pair<ll,ll>p;
set<pair<ll,ll>>se;
int main()
{
  while(scanf("%d",&n)!=EOF)
  {
    if(n==0) return 0;
    printf("Case %d:\n",++cnt);
    se.clear();//每次处理完清空容器
    for(int i=1;i<=n;i++)
    {
      scanf("%s",s);
      scanf("%lld %lld",&p.first,&p.second);
      if(s[0]=='a')
      {
        se.insert(p);
      }
      else
      if(s[0]=='r')
      {
        se.erase(p);
      }
      else
      {
        set<pair<ll,ll>>::iterator it;
        it=se.lower_bound(p);//注意这个函数返回的是迭代器
        bool flag=1;
        for(;it!=se.end();it++)
        {
          if(it->first>p.first&&it->second>p.second)
          {
            flag=0;
            printf("%lld %lld\n",it->first,it->second);
            break;//迭代器要用箭头去访问  
          }
        }
        if(flag==1) printf("-1\n");
      }
    }
    printf("\n");
  }
}
/*
7
1 1
2 3
2 4
3 5
3 4
4 7
5 6
*/