首页 > 代码库 > SRM13绵津见-终(扫描线+线段树/BIT)
SRM13绵津见-终(扫描线+线段树/BIT)
题目大意：求对于每个i求有多少个合法的j以及j对于几个i是合法的，合法的定义：l[i]<=x[j]<=r[i],T[i]-y[i]<=t[j]<=T[i]+y[i]。
设a[i]=T[i]-y[i]，b[i]=T[i]+y[i]。
可以把题目看成一个(x[i],t[i])的点在多少个左上角为(l[i],a[i])右下角为(r[i],b[i])的矩阵中。
那么就从上到下扫每一行，每一行从左到右扫，以横坐标为线段树或BIT下标。
对于询问每个点在多少个矩阵中，可以使用差分，扫到矩阵顶部时+1，矩阵底部时-1（询问完点后再-1或者矩阵底部下一行-1再询问点都可以），那么在扫中间的时候所有点都会+1，单点查询答案即可。
对于询问每个矩阵中有多少个点，扫描线加入点，将询问一个矩阵拆成两个询问，扫到矩阵顶部时候记录下答案，扫到矩阵底部时记录下答案（记录完答案再加入这一行的点或者加入下一行的点前统计下一行的答案都可以），两者相减即为这个矩阵的答案。
BIT的话区间修改还需要差分一下。
线段树：
#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<algorithm>using namespace std;const int maxn=500010,inf=1e9;struct tjm{int sum,delta;}tree[maxn*4];struct poi{int fir,sec,trd,pos,ty;}q[maxn*4];int n,m,cnt,cnt2,N;int x[maxn],t[maxn],T[maxn],y[maxn],lisan[maxn],l[maxn],r[maxn],a[maxn],b[maxn],ans[maxn];void read(int &k){ int f=1;k=0;char c=getchar(); while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar(); while(c<=‘9‘&&c>=‘0‘)k=k*10+c-‘0‘,c=getchar(); k*=f;}bool cmp1(poi a,poi b){return a.fir==b.fir?a.ty>b.ty:a.fir<b.fir;}bool cmp2(poi a,poi b){return a.fir==b.fir?(a.ty==b.ty?a.sec<b.sec:a.ty<b.ty):a.fir<b.fir;}inline void pushup(int x){tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;}inline void pushdown(int x){ if(!tree[x].delta)return; tree[x<<1].delta+=tree[x].delta;tree[x<<1|1].delta+=tree[x].delta; tree[x<<1].sum+=tree[x].delta;tree[x<<1|1].sum+=tree[x].delta; tree[x].delta=0;}void add(int x,int l,int r,int cl,int cr,int delta){ if(cl<=l&&r<=cr){tree[x].sum+=delta;tree[x].delta+=delta;return;} pushdown(x); int mid=(l+r)>>1; if(cl<=mid)add(x<<1,l,mid,cl,cr,delta); if(cr>mid)add(x<<1|1,mid+1,r,cl,cr,delta); pushup(x);}void add2(int x,int l,int r,int cx,int delta){ if(l==r){tree[x].sum+=delta;return;} int mid=(l+r)>>1; if(cx<=mid)add2(x<<1,l,mid,cx,delta); else add2(x<<1|1,mid+1,r,cx,delta); pushup(x);}int query(int x,int l,int r,int cl,int cr){ if(cl<=l&&r<=cr)return tree[x].sum; pushdown(x); int mid=(l+r)>>1,ans=0; if(cl<=mid)ans+=query(x<<1,l,mid,cl,cr); if(cr>mid)ans+=query(x<<1|1,mid+1,r,cl,cr); return ans;}int main(){ read(n);read(m); for(int i=1;i<=n;i++)read(t[i]),read(x[i]),lisan[++cnt2]=t[i]; for(int i=1;i<=m;i++)read(T[i]),read(l[i]),read(r[i]),read(y[i]); for(int i=1;i<=m;i++)a[i]=T[i]-y[i],b[i]=T[i]+y[i]; for(int i=1;i<=m;i++)lisan[++cnt2]=a[i],lisan[++cnt2]=b[i]; N=cnt2;N=unique(lisan+1,lisan+1+N)-lisan-1;sort(lisan+1,lisan+1+N); for(int i=1;i<=m;i++) { a[i]=lower_bound(lisan+1,lisan+1+N,a[i])-lisan; b[i]=lower_bound(lisan+1,lisan+1+N,b[i])-lisan; } for(int i=1;i<=n;i++) t[i]=lower_bound(lisan+1,lisan+1+N,t[i])-lisan; for(int i=1;i<=n;i++)q[++cnt].fir=x[i],q[cnt].sec=t[i],q[cnt].pos=i,q[cnt].ty=0; for(int i=1;i<=m;i++) { q[++cnt].fir=l[i];q[cnt].sec=a[i];q[cnt].trd=b[i];q[cnt].pos=i;q[cnt].ty=1; q[++cnt]=q[cnt-1];q[cnt].fir=r[i];q[cnt].ty=-1; } sort(q+1,q+1+cnt,cmp1); for(int i=1;i<=cnt;i++) { if(q[i].ty)add(1,1,cnt2,q[i].sec,q[i].trd,q[i].ty); else ans[q[i].pos]=query(1,1,cnt2,q[i].sec,q[i].sec); } for(int i=1;i<=n;i++)printf("%d ",ans[i]);printf("\n"); for(int i=1;i<=cnt;i++)if(q[i].ty)q[i].ty=(q[i].ty==-1)?2:-1; memset(tree,0,sizeof(tree));sort(q+1,q+1+cnt,cmp2); for(int i=1;i<=cnt;i++) { if(q[i].ty)ans[q[i].pos]=(q[i].ty==2)?query(1,1,cnt2,q[i].sec,q[i].trd)-ans[q[i].pos]:query(1,1,cnt2,q[i].sec,q[i].trd); else add2(1,1,cnt2,q[i].sec,1); } for(int i=1;i<=m;i++)printf("%d ",ans[i]);}
BIT：
#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<algorithm>using namespace std;const int maxn=500010,inf=1e9;struct poi{int fir,sec,trd,pos,ty;}q[maxn*4];int n,m,cnt,cnt2,N;int x[maxn],t[maxn],T[maxn],y[maxn],lisan[maxn],l[maxn],r[maxn],a[maxn],b[maxn],ans[maxn],tree[maxn];void read(int &k){ int f=1;k=0;char c=getchar(); while(c<‘0‘||c>‘9‘)c==‘-‘&&(f=-1),c=getchar(); while(c<=‘9‘&&c>=‘0‘)k=k*10+c-‘0‘,c=getchar(); k*=f;}bool cmp1(poi a,poi b){return a.fir==b.fir?a.ty>b.ty:a.fir<b.fir;}bool cmp2(poi a,poi b){return a.fir==b.fir?(a.ty==b.ty?a.sec<b.sec:a.ty<b.ty):a.fir<b.fir;}int lowbit(int x){return x&-x;}void add(int x,int delta){for(;x<=cnt2;x+=lowbit(x))tree[x]+=delta;}int query(int x){int ans=0;for(;x;x-=lowbit(x))ans+=tree[x];return ans;}int main(){ read(n);read(m); for(int i=1;i<=n;i++)read(t[i]),read(x[i]),lisan[++cnt2]=t[i]; for(int i=1;i<=m;i++)read(T[i]),read(l[i]),read(r[i]),read(y[i]); for(int i=1;i<=m;i++)a[i]=T[i]-y[i],b[i]=T[i]+y[i]; for(int i=1;i<=m;i++)lisan[++cnt2]=a[i],lisan[++cnt2]=b[i]; N=cnt2;N=unique(lisan+1,lisan+1+N)-lisan-1;sort(lisan+1,lisan+1+N); for(int i=1;i<=m;i++) { a[i]=lower_bound(lisan+1,lisan+1+N,a[i])-lisan; b[i]=lower_bound(lisan+1,lisan+1+N,b[i])-lisan; } for(int i=1;i<=n;i++) t[i]=lower_bound(lisan+1,lisan+1+N,t[i])-lisan; for(int i=1;i<=n;i++)q[++cnt].fir=x[i],q[cnt].sec=t[i],q[cnt].pos=i,q[cnt].ty=0; for(int i=1;i<=m;i++) { q[++cnt].fir=l[i];q[cnt].sec=a[i];q[cnt].trd=b[i];q[cnt].pos=i;q[cnt].ty=1; q[++cnt]=q[cnt-1];q[cnt].fir=r[i];q[cnt].ty=-1; } sort(q+1,q+1+cnt,cmp1); for(int i=1;i<=cnt;i++) { if(q[i].ty)add(q[i].sec,q[i].ty),add(q[i].trd+1,-q[i].ty); else ans[q[i].pos]=query(q[i].sec); } for(int i=1;i<=n;i++)printf("%d ",ans[i]);printf("\n"); for(int i=1;i<=cnt;i++)if(q[i].ty)q[i].ty=(q[i].ty==-1)?2:-1; memset(tree,0,(cnt2+1)<<2);sort(q+1,q+1+cnt,cmp2); for(int i=1;i<=cnt;i++) { if(q[i].ty)ans[q[i].pos]=(q[i].ty==2)?query(q[i].trd)-query(q[i].sec-1)-ans[q[i].pos]:query(q[i].trd)-query(q[i].sec-1); else add(q[i].sec,1); } for(int i=1;i<=m;i++)printf("%d ",ans[i]);}
SRM13绵津见-终(扫描线+线段树/BIT)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。