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.
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.
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.
示例输入
4 add 2 3 find 1 2 remove 2 3 find 1 2 0
示例输出
Case 1: 2 3 -1
提示
来源
2010年山东省第一届ACM大学生程序设计竞赛
STL模板库之set的使用。
这道题没有算法，纯粹是set的使用。
因为要求的数组很大，开数组的话根本开不出来。
【set使用心得】
begin() 返回指向第一个元素的迭代器
ps:迭代器可以理解为“指针”，使用的使用和指针一样使用。
例如：
set <int> s; //定义一个集合set set <int>::iterator it; //定义一个set<int>的迭代器 it = s.begin(); cout<<*it<<endl; //输出迭代器指向的元素的值
或者：
set <pair<int,int>> s; set <pair<int,int>>::iterator it; //定义一个迭代器 it = s.begin(); cout<<it->first<<' '<<it->second<<endl; //输出迭代器指向的元素的值
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 <iostream>
2 #include <stdio.h>
3 #include <set>
4 #include <utility>
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<int,int> > s;
16 set < pair<int,int> >::iterator it; //定义迭代器
17 cout<<"Case "<<cnt<<':'<<endl;
18 for(i=1;i<=n;i++){
19 cin>>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<<endl;
34 else
35 cout<<it->first<<' '<<it->second<<endl;
36 break;
37 default:break;
38 }
39 }
40 cout<<endl;
41 }
42 return 0;
43 }
Freecode : www.cnblogs.com/yym2013