题解 P1847 【轰炸II】

zeromaker · 2015-10-27 08:14:22 · 题解

乍一看这题，和开扇的第一问不是一模一样么？我们只需要维护一个二维树状数组，区间修改，单点查询，@#$%，就可以A过去。但是我们发现题目中还要求求一个东西叫做最后一次被轰炸的轮数，这时候树状数组就不行了，必须要上二维线段树。

对于出题人恶意卡二维树状数组的行为表示很不开心

但是由于这题是完全离线的，其实可以O(N*M)，对于每一个点，我们枚举之前的所有矩形，如果这个点在该矩形的范围内，就把ans++,记录下这个矩形的轮数，由于矩形是按时间顺序排好的，所以这个轮数就是要求的答案，然后直接输出就可以了

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#include<string>
#include<string.h>
using namespace std;

const int Maxn=2010;
struct T
{
    int llx,lly;
    int rrx,rry;
}ju[Maxn];
int n,m;

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&ju[i].llx,&ju[i].lly,&ju[i].rrx,&ju[i].rry);
    }
    for (int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        int ans=0,pos;
        for (int j=1;j<=n;j++)
        {
            if (x>=ju[j].llx && x<=ju[j].rrx && y>=ju[j].lly && y<=ju[j].rry)
            {
                ans++;
                pos=j;
            }
        }
        if (ans==0)
        {
            printf("NO\n");
            continue;
        }
        else
        {
            printf("YES %d %d\n",ans,pos);
        }
    }
}