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;

}

巴特西

HDU 4022 Bombing （map + multiset）

最新文章

热门文章