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

时间：2021-11-07 16:30:52

题意： 给一些平面上的点，然后给一些查询(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[],mb[];

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 = ;

    while(x > ) { 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=;i<=n;i++)

        {

            scanf("%d%d",&p[i].x,&p[i].y);

            a[i] = p[i].x, b[i] = p[i].y;

        }

        for(i=;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+,a+n+m+);

        sort(b+,b+n+m+);

        int inda = unique(a+,a+n+m+)-a-;

        int indb = unique(b+,b+n+m+)-b-;

        maxi = max(inda,indb);

        for(i=;i<=inda;i++) ma[a[i]] = i;

        for(i=;i<=indb;i++) mb[b[i]] = i;

        for(i=;i<=n;i++)    p[i].x = ma[p[i].x], p[i].y = mb[p[i].y];

        for(i=;i<=m;i++)    Q[i].x = ma[Q[i].x], Q[i].y = mb[Q[i].y];

        sort(p+,p+n+,cmp);

        sort(Q+,Q+m+,cmp);

        memset(c1,,sizeof(c1));

        memset(c2,,sizeof(c2));

        for(i=;i<=n;i++)

            modify(c1,p[i].x,);

        j = ;

        for(i=;i<=m;i++)

        {

            while(j <= n && p[j].y <= Q[i].y)

                modify(c2,p[j].x,), j++;

            int LD = getsum(c2,Q[i].x-);

            int UR = getsum(c1,maxi)-getsum(c1,Q[i].x)-(getsum(c2,maxi)-getsum(c2,Q[i].x));

            ans[Q[i].ind] = abs(*(LD+UR)-n);

        }

        for(i=;i<=m;i++) printf("%d\n",ans[i]);

        if(t >= ) puts("");

    }

    return ;

}

直接搞不离散的代码：

#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 = ;

    while(x > ) { 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=;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=;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+,p+n+,cmp);

        sort(Q+,Q+m+,cmp);

        memset(c1,,sizeof(c1));

        memset(c2,,sizeof(c2));

        for(i=;i<=n;i++)

            modify(c1,p[i].x,);

        j = ;

        for(i=;i<=m;i++)

        {

            while(j <= n && p[j].y <= Q[i].y)

                modify(c2,p[j].x,), j++;

            int LD = getsum(c2,Q[i].x-);

            int UR = getsum(c1,maxi)-getsum(c1,Q[i].x)-(getsum(c2,maxi)-getsum(c2,Q[i].x));

            ans[Q[i].ind] = abs(*(LD+UR)-n);

        }

        for(i=;i<=m;i++) printf("%d\n",ans[i]);

        if(t >= ) puts("");

    }

    return ;

}

相关文章