HDU 4022 Bombing （map + multiset）
题意： 在x，y坐标范围为10 ^ -9 ~~ 10 ^ 9的坐标轴之中，有 10W个点（注意有些点可能在同一坐标上），然后有10W个询问，处理询问按照输入顺序处理，对于每个询问a,b a == 0 代表对 x == b轴处理； a == 1 代表 对y == b轴处理。处理即为把该轴上的点全部清空，输出清空的点的数量。已经清空的点，不计算在接下来的询问中。
思路：map + multiset 对于x轴和y轴，分别用两个map 映射，每一个x（或者y）轴都对应着一排点，这些点用multiset存储，为的是在里面二分找需要擦除的y（或者x）上的点。
#include <iostream>#include <algorithm>#include <cmath>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <vector>#include <set>#include <map>#include <queue>#include <stack>#include <climits>//形如INT_MAX一类的#define MAX 100005#define INF 0x7FFFFFFF//#pragma comment(linker, "/STACK:36777216") ///传说中的外挂using namespace std;inline void RD(int &ret) { char c; int flag = 1 ; do { c = getchar(); if(c == '-')flag = -1 ; } while(c < '0' || c > '9') ; ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); ret *= flag ;}void OT(int a) { if(a < 0) { putchar('-'); a = -a; } if(a >= 10)OT(a / 10); putchar(a % 10 + '0');}typedef map<int ,multiset<int> > MP;multiset<int>::iterator it,it2;MP x,y;int n,m;void solvex(int xx) { int size = x[xx].size(); for(it=x[xx].begin(); it != x[xx].end(); it++) { int yy = (*it); it2 = lower_bound(y[yy].begin(), y[yy].end(),xx); while((*it2) == xx) { y[yy].erase(xx); it2 = lower_bound(y[yy].begin(), y[yy].end(),xx); } } OT(size); puts(""); x[xx].clear();}void solvey(int yy) { int size = y[yy].size(); for(it=y[yy].begin(); it != y[yy].end(); it ++) { int xx = (*it); it2 = lower_bound(x[xx].begin(), x[xx].end(),yy); while((*it2) == yy) { x[xx].erase(yy); it2 = lower_bound(x[xx].begin(),x[xx].end(),yy); } } OT(size); puts(""); y[yy].clear();}int main() { int a,b; while(scanf("%d%d",&n,&m) ) { if(n == 0 && m == 0) break; for(int i=0; i<n; i++) { RD(a); RD(b); x[a].insert(b); y[b].insert(a); } for(int i=0; i<m; i++) { RD(a); RD(b); if(a == 0) solvex(b); if(a == 1) solvey(b); } puts(""); } return 0;}