POJ 3416 Crossing解题报告

一、问题描述

题目：

题目大意：如图所示，在平面上有N个点，每个点都有一个坐标，然后在平面上划一条水平线，划一条垂直线，这两条线把平面分成四个区域，计算1区和3区点的和与2区和4区点的和的差的绝对值，即|(a1+a3)-(a2+a4)|，ai表示i区的点数目。点不会落在两条线上。要划M次线，计算每一次划线的结果。(N,M ≤ 50000, 0 ≤x,y ≤ 500000)

 

二、解题思路

由图可知，对于每一次划线，只要求得a2，a12，a23，a1234(分别表示1区的点数量、1区和2区的点数量和，2区和3区的点数量和，所有的点数量)就能求得|(a1+a3)-(a2+a4)|。其中a1=a12-a2; a3=a23-a2;a4=a1234-a12-a3整理后得到|(a1+a3)-(a2+a4)|=|2*a12-4*a2+2*a23|。

定义点的结构

struct Pos

{

       int x;

       int y;

       int index;//该点在输入时的下标（顺序）

};

输入保存在Pos p[]中。

使用一维树状数组C。先将输入各点的坐标和要划的线坐标按y从到大到小进行排序，如果y相等则按x从小到大排序。然后遍历一遍输入数据，如果是index<=N，则修改树状数组C[p[i].x]；如果index>N，则计算a2=Sum(p[i].x)，a12=Sum(xMax)( xMax为输入坐标中x坐标的最大值)。遍历完输入数据后，可以通过树状数组计算a1234=Sum(xMax); a23=Sum(p[ID[i]].x);ID[i]为相应的划线的下标。最后可通过上面公式计算出结果。

三、代码

#include<algorithm>
using namespace std;
int C[500001];    //树状数组
struct Pos
{
    int x;
    int y;
    int index;
};
Pos p[100002];    //保存输入的硬币坐标和划线的坐标
int a2[50002];    //a2[i](i>=1)表示按第i种划线时，2区的硬币数量
int a12[50002];    //a12[i](i>=1)表示按第i种划线时，1区和2区的硬币数量和
int ID[50002];    //ID[i]表示p[]排序后第i组划线在数组中的下标。
int n;            //树状数组的元素个数
int cmp(const void *a,const void *b)
{
    Pos * c=(Pos * )a;
    Pos * d=(Pos * )b;
    if(c->y == d->y)
        return c->x - d->x;
    else
        return d->y - c->y;
}
int Lowbit(int x)
{
    return x&(x^(x-1));
}
void Modify(int i,int x)
{
    while(i<=n)
    {
        C[i]+=x;
        i+=Lowbit(i);
    }
}
int Sum(int i)
{
    int sum=0;
    while(i>0)
    {
        sum+=C[i];
        i-=Lowbit(i);
    }
    return sum;
}
int main()
{
    int T;
    int N,M;
    int t,i;
    int xMax;//最大的x坐标
    scanf("%d",&T);
    for(t=0;t<T;++t)
    {
        memset(C,0,sizeof(C));
        scanf("%d%d",&N,&M);
        xMax=0;
        int total=N+M;
        for(i=0;i<total;++i)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            p[i].x+=1;
            p[i].y+=1;
            p[i].index=i+1;
            if(xMax<p[i].x)
                xMax=p[i].x;
        }
        n=xMax;
        qsort(p,total,sizeof(p[0]),cmp);
        for(i=0;i<total;++i)
        {
            if(p[i].index>N)
            {
                //计算2区硬币数量
                a2[ p[i].index-N ]=Sum(p[i].x);
                //计算1区和2区硬币数量之和
                a12[ p[i].index-N ]=Sum(xMax);
                //将该划线的下标保存起来，用于后面计算a23时使用
                ID[ p[i].index-N ]=i;
            }
            else
            {
                Modify(p[i].x,1);//修改树状数组
            }
        }
        int a1234=Sum(xMax);//计算总和
        for(i=1;i<=M;++i)
        {
            int a23=Sum(p[ID[i]].x);
            int res=2*a12[i]-4*a2[i]+2*a23-a1234;
            if(res<0)
                res*=(-1);
            printf("%d\n",res);
        }
        printf("\n");
    }
    return 0;
}