Bombing
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 3176 Accepted Submission(s): 1195
Problem Description
It’s a cruel war which killed millions of people and ruined series of cities. In order to stop it, let’s bomb the opponent’s base.
It seems not to be a hard work in circumstances of street battles, however, you’ll be encountered a much more difficult instance: recounting exploits of the military. In the bombing action, the commander will dispatch a group of bombers with weapons having the huge destructive power to destroy all the targets in a line. Thanks to the outstanding work of our spy, the positions of all opponents’ bases had been detected and marked on the map, consequently, the bombing plan will be sent to you.
Specifically, the map is expressed as a 2D-plane with some positions of enemy’s bases marked on. The bombers are dispatched orderly and each of them will bomb a vertical or horizontal line on the map. Then your commanded wants you to report that how many bases will be destroyed by each bomber. Notice that a ruined base will not be taken into account when calculating the exploits of later bombers.
It seems not to be a hard work in circumstances of street battles, however, you’ll be encountered a much more difficult instance: recounting exploits of the military. In the bombing action, the commander will dispatch a group of bombers with weapons having the huge destructive power to destroy all the targets in a line. Thanks to the outstanding work of our spy, the positions of all opponents’ bases had been detected and marked on the map, consequently, the bombing plan will be sent to you.
Specifically, the map is expressed as a 2D-plane with some positions of enemy’s bases marked on. The bombers are dispatched orderly and each of them will bomb a vertical or horizontal line on the map. Then your commanded wants you to report that how many bases will be destroyed by each bomber. Notice that a ruined base will not be taken into account when calculating the exploits of later bombers.
Input
Multiple test cases and each test cases starts with two non-negative integer N (N<=100,000) and M (M<=100,000) denoting the number of target bases and the number of scheduled bombers respectively. In the following N line, there is a pair of integers x and y separated by single space indicating the coordinate of position of each opponent’s base. The following M lines describe the bombers, each of them contains two integers c and d where c is 0 or 1 and d is an integer with absolute value no more than 109, if c = 0, then this bomber will bomb the line x = d, otherwise y = d. The input will end when N = M = 0 and the number of test cases is no more than 50.
Output
For each test case, output M lines, the ith line contains a single integer denoting the number of bases that were destroyed by the corresponding bomber in the input. Output a blank line after each test case.
Sample Input
3 2
1 2
1 3
2 3
0 1
1 3
0 0
Sample Output
2
1
Source
wa了两次，原因是在同一个点可能有多个基地。。。
所以用set 是错误的，应该用multiset
然后因为这道题看到了map+set实现离散化的另外一种写法
我的代码：
1 /************************************************************************* 2 > File Name: code/hdoj/4022.cpp 3 > Author: 111qqz 4 > Email: rkz2013@126.com 5 > Created Time: 2015年08月01日 星期六 04时37分20秒 6 ************************************************************************/ 7 8 #include<iostream> 9 #include<iomanip> 10 #include<cstdio> 11 #include<algorithm> 12 #include<cmath> 13 #include<cstring> 14 #include<string> 15 #include<map> 16 #include<set> 17 #include<queue> 18 #include<vector> 19 #include<stack> 20 #define y0 abc111qqz 21 #define y1 hust111qqz 22 #define yn hez111qqz 23 #define j1 cute111qqz 24 #define tm crazy111qqz 25 #define lr dying111qqz 26 using namespace std; 27 #define REP(i, n) for (int i=0;i<int(n);++i) 28 typedef long long LL; 29 typedef unsigned long long ULL; 30 const int N=2E5+7; 31 const int inf = 0x7fffffff; 32 33 map<int,int>xmap,ymap; 34 multiset<int>x[N]; 35 multiset<int>y[N]; 36 int main() 37 { 38 int n,m; 39 while (scanf("%d %d",&n,&m)!=EOF) 40 { 41 if (n==0&&m==0) break; 42 for ( int i = 1 ; i <= n ; i++) 43 { 44 x[i].clear(); 45 y[i].clear(); 46 } 47 xmap.clear(); 48 ymap.clear(); 49 int tx,ty; 50 int cntx=0,cnty=0; 51 for ( int i = 1 ; i <= n ; i++ ) 52 { 53 scanf("%d %d",&tx,&ty); 54 if (!xmap[tx]) xmap[tx]=++cntx; 55 if (!ymap[ty]) ymap[ty]=++cnty; 56 x[xmap[tx]].insert(ymap[ty]); 57 y[ymap[ty]].insert(xmap[tx]); 58 } 59 int c,d; 60 set<int>::iterator it; 61 for ( int i = 1; i <= m ; i++ ) 62 { 63 scanf("%d %d",&c,&d); 64 if (c==0) 65 { 66 cout<<x[xmap[d]].size()<<endl; 67 for ( it = x[xmap[d]].begin();it!=x[xmap[d]].end();it++) 68 { 69 y[*it].erase(xmap[d]); 70 } 71 x[xmap[d]].clear(); 72 } 73 else 74 { 75 cout<<y[ymap[d]].size()<<endl; 76 for ( it =y[ymap[d]].begin();it!=y[ymap[d]].end();it++) 77 { 78 x[*it].erase(ymap[d]); 79 80 } 81 y[ymap[d]].clear(); 82 } 83 } 84 printf(" "); 85 } 86 87 return 0; 88 }
另外一种写法网上的代码（上一道题两种方法都写了，这道题懒得写了啦啦啦，反正都一样）
1 #include<iostream> 2 #include<cstring> 3 #include<string> 4 #include<cstdio> 5 #include<algorithm> 6 #include<map> 7 #include<set> 8 #define maxx 100005 9 using namespace std; 10 typedef map<int,multiset<int> > node; 11 node mx; 12 node my; 13 14 int cal(node &x,node &y,int p) 15 { 16 int res=x[p].size(); 17 multiset<int>::iterator it; 18 for(it=x[p].begin();it!=x[p].end();it++) 19 { 20 //x[p].erase(*it); //不能这样删除，这样删之后it无效 21 y[*it].erase(p); 22 } 23 x[p].clear(); //直接一次清空 24 return res; 25 } 26 27 int main() 28 { 29 int n,m,x,y,q,p; 30 while(scanf("%d%d",&n,&m)) 31 { 32 if(n==0&&m==0) break; 33 mx.clear(); my.clear(); 34 while(n--) 35 { 36 scanf("%d%d",&x,&y); 37 mx[x].insert(y); 38 my[y].insert(x); 39 } 40 while(m--) 41 { 42 scanf("%d%d",&q,&p); 43 if(q==0) printf("%d ",cal(mx,my,p)); 44 else printf("%d ",cal(my,mx,p)); 45 } 46 puts(""); 47 } 48 return 0; 49 }