hdu--4022--multimap<别人用快排+二分,没学好>

本来我是想直接开2个计数数组存下行列各自的元素个数的..

可是数据达到了 10^9 但是数据个数只有10^5 虽然可以考虑用离散化...但我想先map试下毕竟离散化烦~

关于multimap的使用和map还是有点差别的..但是我们单纯地只是使用 stl中的函数的话还是不存在什么难度吧

听说 <<STL源码剖析>>不错...可是不太适合初学者~ =_= 大师经典..

我这题的wa错误太难找了厌死....

我因为一开始想使用数组的原因多此一举地将 c d中的d取绝对值了 ..我也是醉了

还有一个错误...就是待会在代码注释你们将会看到的

在输出 col[x] 与 row[x]后将它们重置为0了这是致命的错误 =_= 因为我的If判断条件是 >=0 那么如果下次又询问到它的时候会导致重复计算该行或列上的点..

就会导致后续的错误.

 1 #include <iostream>
 2 #include <map>
 3 using namespace std;
 4 
 5 multimap<int,int>rowMp;
 6 multimap<int,int>colMp;
 7 map<int,int>row;
 8 map<int,int>col;
 9 
10 int main()
11 {
12     int n , m , op , x , y;
13     while( ~scanf("%d%d",&n,&m) )
14     {
15         if(!n&&!m)
16             break;
17         row.clear();
18         rowMp.clear();
19         col.clear();
20         colMp.clear();
21         while( n-- )
22         {
23             scanf("%d%d",&x,&y);
24             col[x] ++;
25             row[y] ++;
26             colMp.insert( pair<int,int>(x,y) );
27             rowMp.insert( pair<int,int>(y,x) );
28         }
29         multimap<int,int>::iterator rowIt;
30         multimap<int,int>::iterator colIt;
31         while( m-- )
32         {
33             scanf("%d%d",&op,&x);
34             if( op )//y = d  清空行 
35             {
36                 if( row[x]>=0 )
37                 {
38                     printf("%d
",row[x]);
39                     //row[x] = 0;
40                     row[x] = -1;
41                     rowIt = rowMp.find( x );
42                     int num = rowMp.count( x );
43                     while(num--)
44                     {
45                         col[rowIt->second] --;
46                         rowIt ++;
47                     }
48                 }
49                 else
50                 {
51                     printf("0
");
52                 }
53             }
54             else //x = d清空 列 
55             {
56                 if( col[x]>=0 )
57                 {
58                     printf( "%d
",col[x] );
59                     //col[x] = 0;
60                     col[x] = -1;
61                     colIt = colMp.find( x );
62                     int num = colMp.count( x );
63                     while( num-- )
64                     {
65                         row[colIt->second] --;    
66                         colIt ++;            
67                     }
68                 }
69                 else
70                 {
71                     printf("0
");
72                 }
73             }
74         }
75         printf("
");
76     }
77     return 0;
78 }

View Code

我再去学习人家用快排+二分的做法.

today:

　　我是个得意忘形的人

just follow your heart