| WZJ的数据结构（负三十一） |
| 难度级别：D； 运行时间限制：3000ms； 运行空间限制：262144KB； 代码长度限制：2000000B |
|
试题描述
|
|
A国有两个主基站，供给全国的资源。定义一个主基站能覆盖的范围为：以该主基站为圆心，半径为r的圆（包括边界）。
如果一个子基站能被一个主基站覆盖，则它是激活的。 有N个事件，事件分两种： 1.新建一个坐标位于(x,y)的子基站。 2.给出两个主基站的半径：r1、r2。询问处于非激活状态的子基站个数。 |
|
输入
|
|
第一行是四个正整数：x1、y1、x2、y2。表示两个主基站的坐标是（x1,y1）和（x2,y2）。
第二行是一个正整数N，表示有N个事件。 接下来的N行，每行三个正整数。 如果第一个数为1，则接下来两个数为x,y，表示新建一个坐标为（x,y）的新基站。 如果第一个数为2，则接下来两个数为r1,r2，表示询问当两个主基站的覆盖半径为r1和r2时,处于非激活状态的子基站数。 |
|
输出
|
|
对于每个询问输出答案。
|
|
输入示例
|
|
1 10 5 2
10 1 2 6 1 1 9 1 3 8 1 6 7 1 4 12 2 1 1 2 3 2 2 8 2 2 2 2 2 3 2 |
|
输出示例
|
|
4
3 0 4 3 |
|
其他说明
|
|
1<=x1,y1,x2,y2,x,y,r1,r2<=10^9
1<=N<=200000 |
妈妈我会写线段树分治了！
按论文的方法，操作对应一个时间区间，将这个区间打上标记，那么操作的标记数是O(nlogn)的，询问对应一个点，将点所在的区间打上标记，那么询问的标记数也是O(nlogn)的。最后对每一条线段离线做就可以了。
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=200010; ll x0,y0,x1,y1,tmp[maxn]; int n,N,first1[maxn*3],next1[maxn*15],id1[maxn*15],ToT1; int first2[maxn*3],next2[maxn*15],id2[maxn*15],ToT2; struct Query { int tp,id; ll x,y; }Q[maxn]; struct Point { ll x,y;int id; bool operator < (const Point& a) const { if(x!=a.x) return x>a.x; if(y!=a.y) return y>a.y; } }A[maxn]; void pre() { rep(i,1,n) tmp[i]=-Q[i].y; sort(tmp+1,tmp+n+1); rep(i,1,n) Q[i].y=lower_bound(tmp+1,tmp+n+1,-Q[i].y)-tmp; } int ans[maxn],sumv[maxn]; void add(int x,int v) {for(;x<=n;x+=x&-x) sumv[x]+=v;} int sum(int x) {int res=0;for(;x;x-=x&-x) res+=sumv[x];return res;} void query1(int o,int l,int r,int ql,int qr,int v) { if(ql<=l&&r<=qr) { id1[++ToT1]=v;next1[ToT1]=first1[o];first1[o]=ToT1; } else { int mid=l+r>>1,lc=o<<1,rc=lc|1; if(ql<=mid) query1(lc,l,mid,ql,qr,v); if(qr>mid) query1(rc,mid+1,r,ql,qr,v); } } void query2(int o,int l,int r,int x,int v) { id2[++ToT2]=v;next2[ToT2]=first2[o];first2[o]=ToT2; if(l==r) return; int mid=l+r>>1,lc=o<<1,rc=lc|1; if(x<=mid) query2(lc,l,mid,x,v); else query2(rc,mid+1,r,x,v); } int main() { x0=read();y0=read();x1=read();y1=read(); n=read(); rep(i,1,n) { Q[Q[i].id=i].tp=read(); ll x=read(),y=read(); if(Q[i].tp==1) { Q[i].x=(x-x0)*(x-x0)+(y-y0)*(y-y0),Q[i].y=(x-x1)*(x-x1)+(y-y1)*(y-y1); query1(1,1,n,i,n,i); } else { Q[i].x=x*x,Q[i].y=y*y; query2(1,1,n,i,i); } } pre(); rep(i,1,3*n) { int m=0; for(int j=first2[i];j;j=next2[j]) A[++m]=(Point){Q[id2[j]].x,Q[id2[j]].y,Q[id2[j]].id}; for(int j=first1[i];j;j=next1[j]) A[++m]=(Point){Q[id1[j]].x,Q[id1[j]].y,0}; sort(A+1,A+m+1); rep(j,1,m) if(!A[j].id) add(A[j].y,1); else ans[A[j].id]+=sum(A[j].y-1); rep(j,1,m) if(!A[j].id) add(A[j].y,-1); } rep(i,1,n) if(Q[i].tp==2) printf("%d ",ans[i]); return 0; }
CDQ分治常数比较小：
#include<cstdio> #include<cctype> #include<queue> #include<cstring> #include<algorithm> #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define ren for(int i=first[x];i!=-1;i=next[i]) using namespace std; inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } typedef long long ll; const int maxn=200010; ll x0,y0,x1,y1,tmp[maxn]; struct Query { int tp,id; ll x,y; }Q[maxn]; struct Point { ll x,y;int id; bool operator < (const Point& a) const { if(x!=a.x) return x>a.x; if(y!=a.y) return y>a.y; } }A[maxn]; int n,ans[maxn],sumv[maxn]; void add(int x,int v) {for(;x<=n;x+=x&-x) sumv[x]+=v;} int sum(int x) {int res=0;for(;x;x-=x&-x) res+=sumv[x];return res;} void solve(int L,int R) { if(L>=R) return; int mid=L+R>>1,m0=0,m=0; solve(L,mid);solve(mid+1,R); rep(i,L,mid) if(Q[i].tp==1) A[++m0]=(Point){Q[i].x,Q[i].y,0}; if(!m0) return;m=m0; rep(i,mid+1,R) if(Q[i].tp==2) A[++m0]=(Point){Q[i].x,Q[i].y,Q[i].id}; if(m0==m) return;m=m0; sort(A+1,A+m+1); rep(i,1,m) if(!A[i].id) add(A[i].y,1); else ans[A[i].id]+=sum(A[i].y-1); rep(i,1,m) if(!A[i].id) add(A[i].y,-1); } void pre() { rep(i,1,n) tmp[i]=-Q[i].y; sort(tmp+1,tmp+n+1); rep(i,1,n) Q[i].y=lower_bound(tmp+1,tmp+n+1,-Q[i].y)-tmp; } int main() { x0=read();y0=read();x1=read();y1=read(); n=read(); rep(i,1,n) { Q[Q[i].id=i].tp=read(); ll x=read(),y=read(); if(Q[i].tp==1) Q[i].x=(x-x0)*(x-x0)+(y-y0)*(y-y0),Q[i].y=(x-x1)*(x-x1)+(y-y1)*(y-y1); else Q[i].x=x*x,Q[i].y=y*y; } pre();solve(1,n); rep(i,1,n) if(Q[i].tp==2) printf("%d ",ans[i]); return 0; }