【STSRM13】绵津见

【算法】扫描线：差分+树状数组

【题意】转化模型后：求每个矩形覆盖多少点和每个点被多少矩形覆盖。n<=10^5。

【题解】经典的扫描线问题（二维偏序，二维数点）。

数点问题

将所有询问离线并离散化，然后按从上到下排序。

对于点被覆盖问题：

扫描线从上到下进行，遇到矩阵上边界维护区间加，遇到矩阵下边界维护区间减，也就是差分，遇到点单点查询。

每行的排序顺序是｛矩阵加，点，矩阵减｝。

可以线段树区间维护，也可以树状数组每行各自差分。

对于矩阵覆盖问题：

扫描线从上到下进行，遇到点单点加，遇到矩阵上边界查询区间点数，遇到矩阵下边界查询区间点数并减去上边界区间点数得到一个答案。

每行的排序顺序是｛矩阵加，点，矩阵减｝。

线段树和树状数组皆可。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cctype>

using namespace std;

const int maxn=;

struct cyc1{int t,x;}a[maxn];

struct cyc2{int t,l,r,y;}b[maxn];

struct cyc{int x,y,y2,id,kind;}q[maxn];

int t[maxn],n,m,mx,my,tot,c[maxn],d[maxn],ans[maxn];

int read()

{

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

bool cmp(cyc a,cyc b)

{return a.x==b.x?a.kind>b.kind:a.x<b.x;}

bool cmp2(cyc a,cyc b)

{return a.x==b.x?a.kind>b.kind:a.x<b.x;}

int lowbit(int x){return x&(-x);}

void modify(int x,int k){for(int i=x;i<=my;i+=lowbit(i))t[i]+=k;}

int find(int x){int ans=;for(int i=x;i>=;i-=lowbit(i))ans+=t[i];return ans;}

int main(){

    scanf("%d%d",&n,&m);

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

        int u=read(),v=read();

        a[i]=(cyc1){u,v};

        c[++mx]=u;

        d[++my]=v;

    }

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

        int u=read(),v=read(),w=read(),z=read();

        b[i]=(cyc2){u,v,w,z};

        c[++mx]=u-z;c[++mx]=u+z;

        d[++my]=v;d[++my]=w;

    }

    sort(c+,c+mx+);sort(d+,d+my+);

    mx=unique(c+,c+mx+)-c-;

    my=unique(d+,d+my+)-d-;

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

        q[++tot]=(cyc){lower_bound(c+,c+mx+,a[i].t)-c,lower_bound(d+,d+my+,a[i].x)-d,,i,};

    }

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

        q[++tot]=(cyc){lower_bound(c+,c+mx+,b[i].t-b[i].y)-c,lower_bound(d+,d+my+,b[i].l)-d,lower_bound(d+,d+my+,b[i].r)-d,i,};

        tot++;q[tot]=q[tot-];q[tot].x=lower_bound(c+,c+mx+,b[i].t+b[i].y)-c;q[tot].kind=-;

    }

    sort(q+,q+tot+,cmp);

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

        if(q[i].kind){modify(q[i].y,q[i].kind);modify(q[i].y2+,-q[i].kind);}

        else ans[q[i].id]=find(q[i].y);

    }

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

    sort(q+,q+tot+,cmp2);

    memset(t,,sizeof(t));

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

        if(q[i].kind){

            if(q[i].kind==)ans[q[i].id]=find(q[i].y2)-find(q[i].y-);

            else ans[q[i].id]=find(q[i].y2)-find(q[i].y-)-ans[q[i].id];

        }

        else modify(q[i].y,);

    }

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

    return ;

}

巴特西

【STSRM13】绵津见

最新文章

热门文章