Ivan comes again!

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

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.

示例输入

4add 2 3find 1 2remove 2 3find 1 20

示例输出

Case 1:2 3-1

提示

 

来源

 2010年山东省第一届ACM大学生程序设计竞赛

---

 

　　STL模板库之set的使用。

　　这道题没有算法，纯粹是set的使用。

　　因为要求的数组很大，开数组的话根本开不出来。

　　set是集合。可参考：

【set使用心得】begin()　　返回指向第一个元素的迭代器ps:迭代器可以理解为“指针”，使用的使用和指针一样使用。例如：

set 
       
         s;　　//定义一个集合setset 
        
         ::iterator it;    //定义一个set
         
          的迭代器it = s.begin();cout<<*it<
         
        
       

或者：

set 
       
        
         > s;set 
         
          
           >::iterator it;　　//定义一个迭代器it = s.begin();cout<
           
            first<<' '<
            
             second<
            
           
          
         
        
       

clear()　　 清除所有元素count() 　　返回某个值元素的个数empty() 　　如果集合为空，返回true(真）end() 　　  返回指向最后一个元素之后的迭代器，不是最后一个元素equal_range() 　　返回集合中与给定值相等的上下限的两个迭代器ps:某个值的[val)区间的两个值。>=val的第一个值作为下限，>val的第一个值作为上限erase() 　　删除集合中的元素ps:删除值为val的元素直接用s.erase(val);或者可以删除迭代器指向那个元素find() 　　 返回一个指向被查找到元素的迭代器ps:注意返回的是一个迭代器get_allocator() 返回集合的分配器insert()   在集合中插入元素ps:要插入某个元素，直接s.insert(val);即可lower_bound() 　　返回指向大于（或等于）某值的第一个元素的迭代器ps:返回>=val的第一个元素的迭代器key_comp() 　　　　返回一个用于元素间值比较的函数max_size() 　　　　返回集合能容纳的元素的最大限值rbegin() 　返回指向集合中最后一个元素的反向迭代器rend() 　　返回指向集合中第一个元素的反向迭代器size() 　　集合中元素的数目swap() 　　交换两个集合变量upper_bound() 　　返回大于某个值元素的迭代器ps:返回>val的第一个元素的迭代器value_comp() 　　 返回一个用于比较元素间的值的函数

　　这道题拿来熟悉STL很不错。

　　参考博客：

　　代码：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 int main() 7 { 8     int cnt,n; 9     for(cnt=1;cin>>n;cnt++){10         if(n==0) break;11         getchar();12         int i;13         char str[10];14         int a,b;15         set < pair
          
            > s;16         set < pair
           
             >::iterator it; //定义迭代器17 cout<<"Case "<
            
             <<':'<
             
              >str>>a>>b;20 switch(str[0]){21 case 'a':22 s.insert(make_pair(a,b)); //像集合s中插入pair(a,b)23 break;24 case 'r':25 s.erase(make_pair(a,b)); //将集合s中值为pair(a,b)的元素删掉26 break;27 case 'f':28 it = s.upper_bound(make_pair(a,b)); //返回集合中大于pair(a,b)的第一个元素29 for(;it!=s.end();it++) //找到第一个比pair(a,b)大的元素30 if(it->first > a && it->second > b)31 break;32 if(it==s.end())33 cout<<-1<
              
               first<<' '<
               
                second<
               
              
             
            
           
          
         
        
       
      

 

Freecode :