【HDU 5283】【JZOJ 4694】 火神的鱼

Description

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

对于100%的数据1≤T≤10,1≤n,m≤30000,1≤l≤r≤n. 1≤d≤10^9,x1≤x2,y1≤y2。保证任意时刻所有涉及的坐标值在[−10^9,10^9]范围内。

Analysis

。。。 这题也是可以 。。。

留给我一些喘息时间 首先，我在两棵线段树打了一个build，3个query，3个modify，1个down，1个up，1个update。。。 每棵线段树里记录lazy标记， <x1 <script type="math/tex" id="MathJax-Element-3"> <=x2 <script type="math/tex" id="MathJax-Element-4"><=x2</script>的最大值及位置，当前区间答案。。。 打了1.5h，调了3.5h。。。。 从中暴露出一个巨大有用却容易忽视的问题： 码力仍需加强，调试技术欠佳。 这道题有一个不起眼的细节却决定了此题的整个思考方向：鱼只可能往右或往上游。 又因为矩阵固定，所以鱼只要游出了矩阵就永远不可能游回来。 首先，先看x坐标。 先把区间的坐标全部加。 然后查看一下，有没有鱼游进了矩阵，有没有鱼游出了矩阵。进矩阵要满足两个坐标均位于矩阵内，若有，则更新答案，修改上面线段树记录的种种信息；出矩阵只要一个坐标出了就出了，同时可以永久地把该点删掉，修改线段树记录的种种信息。 查询直接查就可以了。 O(mlogn)

Code

#include<cstdio> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int N=30010,INF=2147483647; int n,x1,y1,x2,y2,p1,p2,mp1,mp2,ans[N*4]; struct fish { int x,y; }a[N]; struct segment { int mx,mn,pmx,pmn,lz; //mn:rightest pos lefter than x1 //mx:rightest pos lefter than x2 }tr[2][N*4]; void update(segment &a,int z) { if(a.mx!=-INF) a.mx+=z; if(a.mn!=-INF) a.mn+=z; a.lz+=z; } void up(int p,int v) { if(tr[p][v+v].mn>tr[p][v+v+1].mn) tr[p][v].mn=tr[p][v+v].mn,tr[p][v].pmn=tr[p][v+v].pmn; else tr[p][v].mn=tr[p][v+v+1].mn,tr[p][v].pmn=tr[p][v+v+1].pmn; if(tr[p][v+v].mx>tr[p][v+v+1].mx) tr[p][v].mx=tr[p][v+v].mx,tr[p][v].pmx=tr[p][v+v].pmx; else tr[p][v].mx=tr[p][v+v+1].mx,tr[p][v].pmx=tr[p][v+v+1].pmx; ans[v]=ans[v+v]+ans[v+v+1]; } void down(int p,int v) { if(!tr[p][v].lz) return; int z=tr[p][v].lz; update(tr[p][v+v],z); update(tr[p][v+v+1],z); tr[p][v].lz=0; } void build(int v,int l,int r) { if(l==r) { tr[0][v].pmn=tr[0][v].pmx=tr[1][v].pmn=tr[1][v].pmx=tr[0][v].lz=tr[1][v].lz=ans[v]=0; tr[0][v].mn=tr[0][v].mx=tr[1][v].mn=tr[1][v].mx=-INF; if(x1<=a[l].x && a[l].x<=x2 && y1<=a[l].y && a[l].y<=y2) ans[v]=1; if(a[l].x<x1) tr[0][v].mn=a[l].x,tr[0][v].pmn=l; if(x1<=a[l].x && a[l].x<=x2) tr[0][v].mx=a[l].x,tr[0][v].pmx=l; if(a[l].y<y1) tr[1][v].mn=a[l].y,tr[1][v].pmn=l; if(y1<=a[l].y && a[l].y<=y2) tr[1][v].mx=a[l].y,tr[1][v].pmx=l; return; } tr[0][v].lz=tr[1][v].lz=0; int mid=(l+r)>>1; build(v+v,l,mid); build(v+v+1,mid+1,r); up(0,v),up(1,v); } void change(int p,int v,int l,int r,int x,int y,int z) { if(l==x && r==y) { update(tr[p][v],z); return; } down(p,v); int mid=(l+r)>>1; if(y<=mid) change(p,v+v,l,mid,x,y,z); else if(x>mid) change(p,v+v+1,mid+1,r,x,y,z); else change(p,v+v,l,mid,x,mid,z),change(p,v+v+1,mid+1,r,mid+1,y,z); up(p,v); } void find(int p,int v,int l,int r,int x,int y) { if(l==x && r==y) { if(tr[p][v].mn>mp1) mp1=tr[p][v].mn,p1=tr[p][v].pmn; if(tr[p][v].mx>mp2) mp2=tr[p][v].mx,p2=tr[p][v].pmx; return; } down(p,v); int mid=(l+r)>>1; if(y<=mid) find(p,v+v,l,mid,x,y); else if(x>mid) find(p,v+v+1,mid+1,r,x,y); else find(p,v+v,l,mid,x,mid), find(p,v+v+1,mid+1,r,mid+1,y); up(p,v); } void clear(int p,int v,int l,int r,int x,bool bz) { if(l==r) { tr[p][v].mx=tr[p][v].mn,tr[p][v].pmx=tr[p][v].pmn,tr[p][v].mn=-INF,tr[p][v].pmn=0; if(bz) tr[p][v].mx=-INF,tr[p][v].pmx=0,ans[v]=0; return; } down(0,v),down(1,v); int mid=(l+r)>>1; if(x<=mid) clear(p,v+v,l,mid,x,bz); else clear(p,v+v+1,mid+1,r,x,bz); up(0,v),up(1,v); } void add(int p,int v,int l,int r,int x) { if(l==r) { tr[p][v].mx=tr[p][v].mn,tr[p][v].pmx=tr[p][v].pmn,tr[p][v].mn=-INF,tr[p][v].pmn=0; ans[v]=1; return; } down(0,v),down(1,v); int mid=(l+r)>>1; if(x<=mid) add(p,v+v,l,mid,x); else add(p,v+v+1,mid+1,r,x); up(0,v),up(1,v); } int query(int v,int l,int r,int x,int y) { if(l==x && r==y) return ans[v]; down(0,v),down(1,v); int mid=(l+r)>>1; if(y<=mid) return query(v+v,l,mid,x,y); else if(x>mid) return query(v+v+1,mid+1,r,x,y); else return query(v+v,l,mid,x,mid)+query(v+v+1,mid+1,r,mid+1,y); up(0,v),up(1,v); } bool serch(int p,int v,int l,int r,int x) { if(l==r) return tr[p][v].mn==-INF && tr[p][v].mx!=-INF; down(p,v); int mid=(l+r)>>1; if(x<=mid) return serch(p,v+v,l,mid,x); else return serch(p,v+v+1,mid+1,r,x); up(p,v); } void swim(int p,int l,int r,int z) { change(p,1,1,n,l,r,z); for(mp1=-INF,find(p,1,1,n,l,r);mp1>=(p?y1:x1);mp1=-INF,find(p,1,1,n,l,r)) { bool ok=serch(p^1,1,1,n,p1); if(ok) add(p,1,1,n,p1); else clear(p,1,1,n,p1,0); } for(mp2=-INF,find(p,1,1,n,l,r);mp2>(p?y2:x2);mp2=-INF,find(p,1,1,n,l,r)) clear(0,1,1,n,p2,1),clear(1,1,1,n,p2,1); } int main() { int _,T,tp,l,r,z; scanf("%d",&T); while(T--) { scanf("%d %d %d %d %d",&n,&x1,&y1,&x2,&y2); fo(i,1,n) scanf("%d %d",&a[i].x,&a[i].y); build(1,1,n); scanf("%d",&_); fo(i,1,_) { scanf("%d %d %d",&tp,&l,&r); if(tp==1 || tp==2) { scanf("%d",&z); swim(tp-1,l,r,z); } else printf("%d\n",query(1,1,n,l,r)); } } return 0; }