【HDU5283】【JZOJ4694】火神的鱼

本文主要是介绍【HDU5283】【JZOJ4694】火神的鱼，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

原题是【HDU5283】Senior’s Fish
###Data Constraint
对于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
好像不好下手，树套树？

诶！d值为正，这说明鱼只能向正方向游，那么每条鱼至多进去渔网一次，出来一次。

这样就可以用线段树维护了。

我们对于横坐标和纵坐标分别开一颗线段树，维护两个值，分别是没有进入渔网的最大横坐标（或纵坐标），在渔网内的最大横坐标（或纵坐标），还有区间的答案。

于是就很好维护了，对于每次修改，我们暴力把每个跳进渔网（或跳出渔网）的位置单点修改再重构，由于每个点至多跳进一次跳出一次，所以时间复杂度上是保证的。

###Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define N 100001
#define inf 2147483647
using namespace std;
int a[N],b[N];
int x1,y1,x2,y2;
struct node{int a,b,t;int lz;
}tx[N*4],ty[N*4];
void hb(int v,int l,int r)
{tx[v].t=tx[v*2].t+tx[v*2+1].t;tx[v].a=max(tx[v*2].a,tx[v*2+1].a);tx[v].b=max(tx[v*2].b,tx[v*2+1].b);ty[v].a=max(ty[v*2].a,ty[v*2+1].a);ty[v].b=max(ty[v*2].b,ty[v*2+1].b);tx[v].lz=ty[v].lz=0;
}
void build(int v,int l,int r)
{if(l==r){tx[v].lz=ty[v].lz=0;tx[v].t=0;tx[v].a=tx[v].b=ty[v].a=ty[v].b=-inf;if(a[l]<x1) tx[v].a=a[l];else if(a[l]<=x2) tx[v].b=a[l];if(b[l]<y1) ty[v].a=b[l];else if(b[l]<=y2) ty[v].b=b[l];if(a[l]>=x1 && a[l]<=x2 && b[l]>=y1 && b[l]<=y2) tx[v].t=1;return;}int mid=(l+r)/2;build(v*2,l,mid);build(v*2+1,mid+1,r);hb(v,l,r);
}
void put1(int v,int l,int r)
{if(!tx[v].lz) return;if(tx[v*2].a>-inf) tx[v*2].a+=tx[v].lz;if(tx[v*2+1].a>-inf) tx[v*2+1].a+=tx[v].lz;if(tx[v*2].b>-inf) tx[v*2].b+=tx[v].lz;if(tx[v*2+1].b>-inf) tx[v*2+1].b+=tx[v].lz;tx[v*2].lz+=tx[v].lz;tx[v*2+1].lz+=tx[v].lz;tx[v].lz=0;
}
void put2(int v,int l,int r)
{if(!ty[v].lz) return;if(ty[v*2].a>-inf) ty[v*2].a+=ty[v].lz;if(ty[v*2+1].a>-inf) ty[v*2+1].a+=ty[v].lz;if(ty[v*2].b>-inf) ty[v*2].b+=ty[v].lz;if(ty[v*2+1].b>-inf) ty[v*2+1].b+=ty[v].lz;ty[v*2].lz+=ty[v].lz;ty[v*2+1].lz+=ty[v].lz;ty[v].lz=0;
}
void change1(int v,int l,int r,int x,int y,int z)
{if(l==x && r==y){tx[v].lz+=z;if(tx[v].a>-inf) tx[v].a+=z;if(tx[v].b>-inf) tx[v].b+=z;return;}put1(v,l,r);put2(v,l,r);int mid=(l+r)/2;if(y<=mid) change1(v*2,l,mid,x,y,z);else if(x>mid) change1(v*2+1,mid+1,r,x,y,z);else{change1(v*2,l,mid,x,mid,z);change1(v*2+1,mid+1,r,mid+1,y,z);}hb(v,l,r);
}
void change2(int v,int l,int r,int x,int y,int z)
{if(l==x && r==y){ty[v].lz+=z;if(ty[v].a>-inf) ty[v].a+=z;if(ty[v].b>-inf) ty[v].b+=z;return;}put1(v,l,r);put2(v,l,r);int mid=(l+r)/2;if(y<=mid) change2(v*2,l,mid,x,y,z);else if(x>mid) change2(v*2+1,mid+1,r,x,y,z);else{change2(v*2,l,mid,x,mid,z);change2(v*2+1,mid+1,r,mid+1,y,z);}hb(v,l,r);
}
int find(int v,int l,int r,int x,int y)
{if(l==x && r==y) return tx[v].t;put1(v,l,r);put2(v,l,r);int mid=(l+r)/2;if(y<=mid) return find(v*2,l,mid,x,y);else if(x>mid) return find(v*2+1,mid+1,r,x,y);else return find(v*2,l,mid,x,mid)+find(v*2+1,mid+1,r,mid+1,y);
}
void del(int v,int l,int r,int op)
{if(l==r){tx[v].a=tx[v].b=ty[v].a=ty[v].b=-inf;tx[v].t=0;return;}put1(v,l,r);put2(v,l,r);int mid=(l+r)/2;if(op==1){if(tx[v*2].b>x2) del(v*2,l,mid,op);else del(v*2+1,mid+1,r,op);}else{if(ty[v*2].b>y2) del(v*2,l,mid,op);else del(v*2+1,mid+1,r,op);}hb(v,l,r);
}
void add(int v,int l,int r,int op)
{if(l==r){if(op==1){if(ty[v].b>=y1 && ty[v].b<=y2) tx[v].t=1;else tx[v].t=0;tx[v].b=tx[v].a,tx[v].a=-inf;}else{if(tx[v].b>=x1 && tx[v].b<=x2) tx[v].t=1;else tx[v].t=0;ty[v].b=ty[v].a,ty[v].a=-inf;}return;}put1(v,l,r);put2(v,l,r);int mid=(l+r)/2;if(op==1){if(tx[v*2].a>=x1) add(v*2,l,mid,op);else add(v*2+1,mid+1,r,op);}else{if(ty[v*2].a>=y1) add(v*2,l,mid,op);else add(v*2+1,mid+1,r,op);}hb(v,l,r);
}
int main()
{freopen("3.in","r",stdin);freopen("3.out","w",stdout);int T;cin>>T;while(T--){int n;scanf("%d",&n);scanf("%d %d %d %d",&x1,&y1,&x2,&y2);fo(i,1,n) scanf("%d %d",&a[i],&b[i]);build(1,1,n);int m;scanf("%d",&m);while(m--){int q;scanf("%d",&q);if(q==1){int l,r,x;scanf("%d %d %d",&l,&r,&x);change1(1,1,n,l,r,x);while(tx[1].a>=x1) add(1,1,n,1);while(tx[1].b>x2) del(1,1,n,1);}else if(q==2){int l,r,x;scanf("%d %d %d",&l,&r,&x);change2(1,1,n,l,r,x);while(ty[1].a>=y1) add(1,1,n,2);while(ty[1].b>y2) del(1,1,n,2);}else{int l,r;scanf("%d %d",&l,&r);printf("%d\n",find(1,1,n,l,r));}}}
}