[JZOJ4694] 火神的鱼 [HDU5283] Senior's Fish

Description

火神最爱的就是吃鱼了，所以某一天他来到了一个池塘边捕鱼。池塘可以看成一个二维的平面，而他的渔网可以看成一个与坐标轴平行的矩形。 池塘里的鱼不停地在水中游动，可以看成一些点。有的时候会有鱼游进渔网，有的时候也会有鱼游出渔网。所以火神不知道什么时候收网才可以抓住最多的鱼，现在他寻求你的帮助。 他对池塘里的每条鱼都给予了一个标号，分别从1到n标号，n表示池塘里鱼的总数。鱼的游动可以概括为两个动作： 1 l r d : 表示标号在[l，r]这个区间内的鱼向x轴正方向游动了d个单位长度。 2 l r d：表示标号在[l，r]这个区间内的鱼向y轴正方向游动了d个单位长度。 在某些时刻火神会询问你现在有多少条他关心的鱼在渔网内(边界上的也算)，请你来帮助他吧。 对于30%的数据1≤n,m≤1000 对于100%的数据1≤T≤10,1≤n,m≤30000,1≤l≤r≤n. 1≤d≤10^9,x1≤x2,y1≤y2。保证任意时刻所有涉及的坐标值在[−10^9,10^9]范围内。

Solution

观察题目，我们应该用数据结构来维护。

对于 x 坐标和y坐标，分别维护一棵线段树，维护不超过 x1(y1) 的 x(y) 最大值（设为 l ）和不超过x2(y2)的 x(y) 最大值（设为 r ）

另开一个树状数组，维护区间答案。

对于加操作，直接在对应的线段树上更改，如果当前l>=x1，说明它 x 坐标已经进入了合法区间，在l中删去， r 中加上，如果r>x2，那就将这个点删掉，同时根据这个点在 y <script type="math/tex" id="MathJax-Element-937">y</script>中的情况判断是否修改树状数组的答案。

Code

#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<iostream> #define fo(i,a,b) for(i=a;i<=b;i++) #define fod(i,a,b) for(i=a;i>=b;i--) #define inf 1100000000 using namespace std; struct node { int ls,rs,lx,lw,rx,rw; }tr[600005]; int a[30005][2],n,m,x,y,x2,y2,t,nd,c[300005],lazy[600005][2]; bool bz[30005][2]; int lowbit(int x) { return (x&-x); } int gets(int k) { int s=0; while (k>0) { s+=c[k]; k-=lowbit(k); } return s; } void change(int k,int v) { while (k<=300000) { c[k]+=v; k+=lowbit(k); } } void down(int now,int l,int mid,int r) { int ls=tr[now].ls,rs=tr[now].rs; if (lazy[now][0]!=0) { tr[ls].lx+=lazy[now][0]; tr[rs].lx+=lazy[now][0]; lazy[ls][0]+=lazy[now][0]; lazy[rs][0]+=lazy[now][0]; lazy[now][0]=0; } if (lazy[now][1]!=0) { tr[ls].rx+=lazy[now][1]; tr[rs].rx+=lazy[now][1]; lazy[ls][1]+=lazy[now][1]; lazy[rs][1]+=lazy[now][1]; lazy[now][1]=0; } } void up(int now,int ls,int rs) { tr[now].lx=max(tr[ls].lx,tr[rs].lx); tr[now].lw=(tr[now].lx==tr[ls].lx)?tr[ls].lw:tr[rs].lw; tr[now].rx=max(tr[ls].rx,tr[rs].rx); tr[now].rw=(tr[now].rx==tr[ls].rx)?tr[ls].rw:tr[rs].rw; } void build(int now,int l,int r,int v) { if(l==r) { tr[now].lx=tr[now].rx=-inf; tr[now].lw=tr[now].rw=-1; if (a[l][0]>x2||a[l][1]>y2) return; if(v==0) { if (a[l][0]<x) tr[now].lx=a[l][0],tr[now].lw=l; else if (a[l][0]<=x2) tr[now].rx=a[l][0],tr[now].rw=l; } else { if (a[l][1]<y) tr[now].lx=a[l][1],tr[now].lw=l; else if (a[l][1]<=y2) tr[now].rx=a[l][1],tr[now].rw=l; } return; } int mid=(l+r)/2,ls,rs; ls=tr[now].ls=++nd; build(nd,l,mid,v); rs=tr[now].rs=++nd; build(nd,mid+1,r,v); up(now,ls,rs); } void change1(int now,int l,int r,int x,int y,int v1,int v2) { if (l==x&&r==y) { if (tr[now].lx!=-inf) tr[now].lx+=v1; if (tr[now].rw==-1) { if(v2!=-inf&&v1==-inf) tr[now].rx=v2,tr[now].rw=l; } else tr[now].rx+=v2; lazy[now][0]+=v1; lazy[now][1]+=v2; if (v1==-inf) tr[now].lw=0; if (v2==-inf) tr[now].rw=0; return; } int ls=tr[now].ls,rs=tr[now].rs,mid=(l+r)/2; down(now,ls,mid,rs); if (y<=mid) change1(ls,l,mid,x,y,v1,v2); else if(x>mid) change1(rs,mid+1,r,x,y,v1,v2); else { change1(ls,l,mid,x,mid,v1,v2); change1(rs,mid+1,r,mid+1,y,v1,v2); } up(now,ls,rs); } void find(int now,int l,int r,int x,int y,int &lx,int &lw,int &rx,int &rw) { if (l==x&&r==y) { lx=tr[now].lx; lw=tr[now].lw; rx=tr[now].rx; rw=tr[now].rw; return; } int ls=tr[now].ls,rs=tr[now].rs,mid=(l+r)/2; down(now,ls,mid,rs); if (y<=mid) find(ls,l,mid,x,y,lx,lw,rx,rw); else if (x>mid) find(rs,mid+1,r,x,y,lx,lw,rx,rw); else { int l1,l2,r1,r2; find(ls,l,mid,x,mid,lx,lw,rx,rw); find(rs,mid+1,r,mid+1,r,l1,l2,r1,r2); lx=max(l1,lx); if (lx==l1) lw=l2; rx=max(r1,rx); if (rx==r1) rw=r2; } up(now,ls,rs); } int main() { cin>>t; while (t-->0) { int i,j; scanf("%d",&n); scanf("%d%d%d%d",&x,&y,&x2,&y2); memset(bz,0,sizeof(bz)); memset(c,0,sizeof(c)); memset(lazy,0,sizeof(lazy)); fo(i,1,n) { scanf("%d%d",&a[i][0],&a[i][1]); if (a[i][0]<=x2&&a[i][0]>=x) bz[i][0]=1; if (a[i][1]<=y2&&a[i][1]>=y) bz[i][1]=1; if (bz[i][0]&&bz[i][1]) change(i,1); } nd=2; build(1,1,n,0); build(2,1,n,1); int lm,lz,rz,rm; find(1,1,n,1,n,lm,lz,rm,rz); scanf("%d",&m); fo(i,1,m) { int p,l,r,d,s=0; scanf("%d%d%d",&p,&l,&r); if (p==3) printf("%d\n",gets(r)-gets(l-1)); else { scanf("%d",&d); if (p==1) { change1(1,1,n,l,r,d,d); find(1,1,n,l,r,lm,lz,rm,rz); while (lm>=x&&lz>0) { change1(1,1,n,lz,lz,-inf,lm); bz[lz][0]=1; if(bz[lz][1]==1) change(lz,1); find(1,1,n,l,r,lm,lz,rm,rz); } while (rm>x2&&rz>0) { change1(1,1,n,rz,rz,0,-inf); bz[rz][0]=0; if(bz[rz][1]==1) change(rz,-1); find(1,1,n,l,r,lm,lz,rm,rz); } } else { change1(2,1,n,l,r,d,d); find(2,1,n,l,r,lm,lz,rm,rz); while (lm>=y&&lz>0) { change1(2,1,n,lz,lz,-inf,lm); bz[lz][1]=1; if(bz[lz][0]==1) change(lz,1); find(2,1,n,l,r,lm,lz,rm,rz); } while (rm>y2&&rz>0) { change1(2,1,n,rz,rz,0,-inf); bz[rz][1]=0; if(bz[rz][0]==1) change(rz,-1); find(2,1,n,l,r,lm,lz,rm,rz); } } } } } }