POJ 3416 Crossing --离线+树状数组

浏览数：14 / 时间：2015年06月08日

题意：给一些平面上的点，然后给一些查询(x,y)，即以(x,y)为原点建立坐标系，一个人拿走第I,III象限的点，另一个人拿II,IV象限的，点不会在任何一个查询的坐标轴上，问每次两人的点数差为多少。

解法：离线树状数组。点不在坐标轴上，即点不共线使这题简单了不少，可以离散化点，也可以不离散化，因为x,y <= 500000，直接就可以搞。我这里是离散的，其实也没比直接搞快。

见两个树状数组，一个先把所有点都modify进去，一个等待以后加元素。

然后将查询和给出的点都按y坐标排序，然后离线对每个查询执行操作了。每次查询前把y坐标小于当前查询点的点加入树状数组。

这时的左下角点数即为： LD = getsum(c2,Q[i].x-1);

右上角： UR = getsum(c1,maxi)-getsum(c1,Q[i].x)-(getsum(c2,maxi)-getsum(c2,Q[i].x)); 即为整个右边的个数减去y坐标小于此点的（即为右下角）。

那么另两个象限的综述就是 n-LD-UR。

这样就解决了。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 100007

struct node{
    int x,y,ind;
}p[N],Q[N];
int n,m,maxi;
int c1[N],c2[N],a[N],b[N],ans[N];
int ma[500008],mb[500008];
int lowbit(int x) { return x&-x; }
int cmp(node ka,node kb) { return ka.y < kb.y; }

void modify(int *c,int x,int val)
{
    while(x <= maxi)
        c[x] += val, x += lowbit(x);
}

int getsum(int *c,int x)
{
    int res = 0;
    while(x > 0) { res += c[x]; x -= lowbit(x); }
    return res;
}

int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            a[i] = p[i].x, b[i] = p[i].y;
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&Q[i].x,&Q[i].y);
            a[i+n] = Q[i].x, b[i+n] = Q[i].y;
            Q[i].ind = i;
        }
        sort(a+1,a+n+m+1);
        sort(b+1,b+n+m+1);
        int inda = unique(a+1,a+n+m+1)-a-1;
        int indb = unique(b+1,b+n+m+1)-b-1;
        maxi = max(inda,indb);
        for(i=1;i<=inda;i++) ma[a[i]] = i;
        for(i=1;i<=indb;i++) mb[b[i]] = i;

        for(i=1;i<=n;i++)    p[i].x = ma[p[i].x], p[i].y = mb[p[i].y];
        for(i=1;i<=m;i++)    Q[i].x = ma[Q[i].x], Q[i].y = mb[Q[i].y];
        sort(p+1,p+n+1,cmp);
        sort(Q+1,Q+m+1,cmp);
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        for(i=1;i<=n;i++)
            modify(c1,p[i].x,1);
        j = 1;
        for(i=1;i<=m;i++)
        {
            while(j <= n && p[j].y <= Q[i].y)
                modify(c2,p[j].x,1), j++;
            int LD = getsum(c2,Q[i].x-1);
            int UR = getsum(c1,maxi)-getsum(c1,Q[i].x)-(getsum(c2,maxi)-getsum(c2,Q[i].x));
            ans[Q[i].ind] = abs(2*(LD+UR)-n);
        }
        for(i=1;i<=m;i++) printf("%d\n",ans[i]);
        if(t >= 1) puts("");
    }
    return 0;
}

View Code

直接搞不离散的代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
#define N 500007

struct node{
    int x,y,ind;
}p[N],Q[N];
int n,m,maxi;
int c1[N],c2[N],a[N],b[N],ans[N];
int lowbit(int x) { return x&-x; }
int cmp(node ka,node kb) { return ka.y < kb.y; }

void modify(int *c,int x,int val)
{
    while(x <= maxi)
        c[x] += val, x += lowbit(x);
}

int getsum(int *c,int x)
{
    int res = 0;
    while(x > 0) { res += c[x]; x -= lowbit(x); }
    return res;
}

int main()
{
    int i,j,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&p[i].x,&p[i].y);
            p[i].x++, p[i].y++;
            maxi = max(maxi,p[i].x);
        }
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&Q[i].x,&Q[i].y);
            Q[i].x++, Q[i].y++;
            Q[i].ind = i;
            maxi = max(maxi,Q[i].x);
        }
        sort(p+1,p+n+1,cmp);
        sort(Q+1,Q+m+1,cmp);
        memset(c1,0,sizeof(c1));
        memset(c2,0,sizeof(c2));
        for(i=1;i<=n;i++)
            modify(c1,p[i].x,1);
        j = 1;
        for(i=1;i<=m;i++)
        {
            while(j <= n && p[j].y <= Q[i].y)
                modify(c2,p[j].x,1), j++;
            int LD = getsum(c2,Q[i].x-1);
            int UR = getsum(c1,maxi)-getsum(c1,Q[i].x)-(getsum(c2,maxi)-getsum(c2,Q[i].x));
            ans[Q[i].ind] = abs(2*(LD+UR)-n);
        }
        for(i=1;i<=m;i++) printf("%d\n",ans[i]);
        if(t >= 1) puts("");
    }
    return 0;
}