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

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

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

數(shù)點問題

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

對于點被覆蓋問題：

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

每行的排序順序是｛矩陣加，點，矩陣減｝。

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

對于矩陣覆蓋問題：

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

每行的排序順序是｛矩陣加，點，矩陣減｝。

線段樹和樹狀數(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("\n");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

?

轉(zhuǎn)載于:https://www.cnblogs.com/onioncyc/p/7348096.html

總結(jié)

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

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