gym101964G Matrix Queries seerc2018k题 cdq分治

题目大意：

　　二维平面上有q次操作，每次操作可以是添加一个点，也可以是添加一个矩形，问每次操作后，有多少点-矩形这样的pair，pair的条件是点被矩形覆盖（边缘覆盖也算）。

思路：

　　cdq分治，由于加点和加矩形都既是修改操作又是查询操作，而且两种方式完全不一样，所以用两部分cdq来写。

　　先将矩形拆成四个点，并且向左下角扩展一个单元，左下角和右上角的点的权值赋为1，左上角和右下角赋为-1。

　　对于加矩形的操作，遇到加的点则修改树状数组，遇到矩形的点查询小于这个矩形的值，并且乘以这个矩形点的权值。

　　对于加点的操作，由于往左下角扩展了，所以应该按x从右往左处理，碰到一个矩形点，更新树状数组，碰到加的点，则ans+=sum（m）-sum（y-1），m是y的上界，因为sum(m)是刚好抵消的情况（等于0），而sum（y-1）则代表了有几个矩形的右下角在这个点的下方。

　　（还是看代码比较好写，注意树状数组的上界，sum（m）不要作死的用sum（m+1）代替，因为这个自闭了）。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int q,tot,m,brr[maxn<<],maxd;

long long ans[maxn],res[maxn<<];

struct node{

    int id,x,y,type,val;

}a[maxn<<],b[maxn<<];

inline void Hash(){

    sort(brr+,brr++m);

    m=unique(brr+,brr++m)-brr-;

    for(int i=;i<=tot;i++)

    {

        a[i].x=lower_bound(brr+,brr++m,a[i].x)-brr;

        a[i].y=lower_bound(brr+,brr++m,a[i].y)-brr;

        maxd=max(maxd,a[i].y);

    }

}

inline void add(int x,int v){

    while(x<=m){res[x]+=v, x+= x & (-x);}

}

inline long long  sum(int x){

    long long tu=;

    while(x>){tu+=res[x], x -= x & (-x);}

    return tu;

}

inline bool cmpx(const node &a,const node &b){

    if(a.x!=b.x)return a.x<b.x;

    return a.id<b.id;

}

inline bool cmpx2(const node &a,const node &b){

    if(a.x!=b.x)return a.x>b.x;

    return a.id<b.id;

}

inline void cdq1(int l,int r){//加点

    if(l==r)return ;

    int mid=l+((r-l)>>);

//    printf("l:%d r:%d  mid:%d\n",l,r,mid);

    cdq1(l,mid),cdq1(mid+,r);

    int cc=;

    for(int i=l;i<=mid;i++)

    {

        b[++cc]=a[i];

        b[cc].id=;

    }

    for(int i=mid+;i<=r;i++)

    {

        b[++cc]=a[i];

    }

    sort(b+,b++cc,cmpx2);

    for(int i=;i<=cc;i++)

    {

        if(b[i].id==){

            if(b[i].type==)continue;

            add(b[i].y,b[i].val);

        //    printf("y:%d  val:%d\n",b[i].y,b[i].val);

        }else{

            if(b[i].type==)continue;

            ans[b[i].id]+=sum(m)-sum(b[i].y-);//**sum(m+1)

        }

    }

    for(int i=;i<=cc;i++)

    {

        if(b[i].id==&&b[i].type==)add(b[i].y,-b[i].val);

    }

}

inline void cdq2(int l,int r){//加矩形

    if(l==r)return ;

    int mid=l+((r-l)>>);

    cdq2(l,mid),cdq2(mid+,r);

    int cc=;

    for(int i=l;i<=mid;i++)

    {

        b[++cc]=a[i];

        b[cc].id=;

    }

    for(int i=mid+;i<=r;i++)

    {

        b[++cc]=a[i];

    }

    sort(b+,b++cc,cmpx);

    for(int i=;i<=cc;i++)

    {

        if(b[i].id==){

            if(b[i].type==)continue;

            add(b[i].y,);

        }else{

            if(b[i].type==)continue;

            ans[b[i].id]+=sum(b[i].y)*b[i].val;

        }

    }

    for(int i=;i<=cc;i++)

    {

        if(b[i].id==&&b[i].type==)add(b[i].y,-);

    }

}

int main(){

    scanf("%d",&q);

    tot=;

    for(int i=;i<=q;i++)

    {

        int type,x1,y1,x2,y2;

        scanf("%d",&type);

        a[++tot].type=type;

        a[tot].id=i;

        if(a[tot].type==)

        {

            scanf("%d%d",&x1,&y1);

            a[tot].x=x1,a[tot].y=y1;

            brr[++m]=x1,brr[++m]=y1;

        }

        else

        {

            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

            x1--,y1--;//tuo zhan ju xin

            brr[++m]=x1,brr[++m]=x2,brr[++m]=y1,brr[++m]=y2;

            a[tot].x=x1,a[tot].y=y1,a[tot].val=;

            a[++tot].x=x1,a[tot].y=y2,a[tot].val=-,a[tot].type=type,a[tot].id=i;

            a[++tot].x=x2,a[tot].y=y2,a[tot].val=,a[tot].type=type,a[tot].id=i;

            a[++tot].x=x2,a[tot].y=y1,a[tot].val=-,a[tot].type=type,a[tot].id=i;

        }

    }

    Hash();

    cdq2(,tot);

    cdq1(,tot);

    for(int i=;i<=q;i++)

    {

        ans[i]=ans[i]+ans[i-];

    printf("%lld\n",ans[i]);

    }

}

巴特西

gym101964G Matrix Queries seerc2018k题 cdq分治

最新文章

热门文章