【算法】掃描線：差分+樹狀數(shù)組

【題意】轉(zhuǎn)化模型后：求每個(gè)矩形覆蓋多少點(diǎn)和每個(gè)點(diǎn)被多少矩形覆蓋。n<=10^5。

【題解】經(jīng)典的掃描線問題（二維偏序，二維數(shù)點(diǎn)）。

數(shù)點(diǎn)問題

將所有詢問離線并離散化，然后按從上到下排序。

對(duì)于點(diǎn)被覆蓋問題：

掃描線從上到下進(jìn)行，遇到矩陣上邊界維護(hù)區(qū)間加，遇到矩陣下邊界維護(hù)區(qū)間減，也就是差分，遇到點(diǎn)單點(diǎn)查詢。

每行的排序順序是｛矩陣加，點(diǎn)，矩陣減｝。

可以線段樹區(qū)間維護(hù)，也可以樹狀數(shù)組每行各自差分。

對(duì)于矩陣覆蓋問題：

掃描線從上到下進(jìn)行，遇到點(diǎn)單點(diǎn)加，遇到矩陣上邊界查詢區(qū)間點(diǎn)數(shù)，遇到矩陣下邊界查詢區(qū)間點(diǎn)數(shù)并減去上邊界區(qū)間點(diǎn)數(shù)得到一個(gè)答案。

每行的排序順序是｛矩陣加，點(diǎn)，矩陣減｝。

線段樹和樹狀數(shù)組皆可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
using namespace std;
const int maxn=300010;
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=0,t=1;
    while(!isdigit(c=getchar()))if(c=='-')t=-1;
    do{s=s*10+c-'0';}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=0;for(int i=x;i>=1;i-=lowbit(i))ans+=t[i];return ans;}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        int u=read(),v=read();
        a[i]=(cyc1){u,v};
        c[++mx]=u;
        d[++my]=v;
    }
    for(int i=1;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+1,c+mx+1);sort(d+1,d+my+1);
    mx=unique(c+1,c+mx+1)-c-1;
    my=unique(d+1,d+my+1)-d-1;
    for(int i=1;i<=n;i++){
        q[++tot]=(cyc){lower_bound(c+1,c+mx+1,a[i].t)-c,lower_bound(d+1,d+my+1,a[i].x)-d,0,i,0};
    }
    for(int i=1;i<=m;i++){
        q[++tot]=(cyc){lower_bound(c+1,c+mx+1,b[i].t-b[i].y)-c,lower_bound(d+1,d+my+1,b[i].l)-d,lower_bound(d+1,d+my+1,b[i].r)-d,i,1};
        tot++;q[tot]=q[tot-1];q[tot].x=lower_bound(c+1,c+mx+1,b[i].t+b[i].y)-c;q[tot].kind=-1;
    }
    sort(q+1,q+tot+1,cmp);
    for(int i=1;i<=tot;i++){
        if(q[i].kind){modify(q[i].y,q[i].kind);modify(q[i].y2+1,-q[i].kind);}
        else ans[q[i].id]=find(q[i].y);
    }
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);printf("
");
    sort(q+1,q+tot+1,cmp2);
    memset(t,0,sizeof(t));
    for(int i=1;i<=tot;i++){
        if(q[i].kind){
            if(q[i].kind==1)ans[q[i].id]=find(q[i].y2)-find(q[i].y-1);
            else ans[q[i].id]=find(q[i].y2)-find(q[i].y-1)-ans[q[i].id];
        }
        else modify(q[i].y,1);
    }
    for(int i=1;i<=m;i++)printf("%d ",ans[i]);
    return 0;
}

View Code

總結(jié)

以上是生活随笔為你收集整理的【STSRM13】绵津见的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。