【hdu5283】火神的鱼

Description

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

Solution

一开始因为不知道处理了x之后，怎么快速的把y也处理掉，好像必须要log的速度。 然而时间限制是5秒啊。 这题本来很简单的，农味有点重。 渔网上有四个点，我们用类似前缀和的求答案，就是说维护每个点的左下角有多少个点。 那么就给每个点开两棵线段树，一个维护x另一个维护y，只维护在要求区间内的点。 然后在区间加的时候，有些点会超出区间范围，那么怎么去找这些点呢？ 我们维护一个权值最大的点，如果区间[l,r]加u，先让他们+u之后再去询问，如果当前权值最大的点超出的范围，就把权值改为-maxlongint，那么因为维护x的线段树中这个点已经不合法了，那么在维护y的这个线段树中的这个点也不要了(权值改为-maxlongint)。

Code

#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; const int maxn=30007; int i,j,k,l,n,m,ans,cas,r,u,gg,shi; int a[5][2],b[8][maxn]; bool bz[2][maxn]; struct node{ int da,sum,daz,biao; }t[8][maxn*3]; void merge(int o,int x){ t[o][x].daz=max(t[o][x*2].daz,t[o][x*2+1].daz); t[o][x].da=(t[o][x*2].daz>t[o][x*2+1].daz)?t[o][x*2].da:t[o][x*2+1].da; t[o][x].sum=t[o][x*2].sum+t[o][x*2+1].sum; } void build(int o,int x,int l,int r){ t[o][x].biao=0; t[o][x].da=t[o][x].sum=0; t[o][x].daz=-0x7fffffff; if(l==r){ t[o][x].da=l;t[o][x].daz=b[o][l];t[o][x].sum=(b[o][l]!=gg)?1:0; return; } int mid=(l+r)/2; build(o,x*2,l,mid); build(o,x*2+1,mid+1,r); merge(o,x); } void down(int o,int x){ if(t[o][x].biao){ t[o][x*2].biao+=t[o][x].biao; t[o][x*2+1].biao+=t[o][x].biao; t[o][x*2].daz+=t[o][x].biao; t[o][x*2+1].daz+=t[o][x].biao; t[o][x].biao=0; } } void gai(int o,int x,int l,int r,int y){ if(l==r){ t[o][x].daz=-0x7fffffff,t[o][x].sum=0; if(t[o^1][x].sum)gai(o^1,1,1,n,l); return; } down(o,x); int mid=(l+r)/2; if(y<=mid)gai(o,x*2,l,mid,y); else gai(o,x*2+1,mid+1,r,y); merge(o,x); } void change(int o,int x,int l,int r,int y,int z,int u){ shi++; // if(!t[o][x].sum)return; if(l==y&&r==z){ t[o][x].daz+=u,t[o][x].biao+=u; return; } down(o,x); int mid=(l+r)/2; if(z<=mid)change(o,x*2,l,mid,y,z,u); else if(y>mid)change(o,x*2+1,mid+1,r,y,z,u); else{ change(o,x*2,l,mid,y,mid,u);change(o,x*2+1,mid+1,r,mid+1,z,u); } merge(o,x); } void find(int o,int x,int l,int r,int y,int z,int u){ change(o,x,l,r,y,z,u); while(t[o][x].daz>a[o/2][o%2]){ gai(o,1,1,n,t[o][x].da); } } int getans(int x,int l,int r,int y,int z){ if(l==y&&r==z){ return t[0][x].sum-t[2][x].sum-t[4][x].sum+t[6][x].sum; } down(0,x);down(2,x);down(4,x);down(6,x); down(1,x);down(3,x);down(5,x);down(7,x); int mid=(l+r)/2; if(z<=mid)return getans(x*2,l,mid,y,z); else if(y>mid)return getans(x*2+1,mid+1,r,y,z); else{ return getans(x*2,l,mid,y,mid)+getans(x*2+1,mid+1,r,mid+1,z); } } int main(){ // freopen("fan.in","r",stdin); // freopen("fan.out","w",stdout); for(scanf("%d",&cas);cas;cas--){ scanf("%d",&n); scanf("%d%d%d%d",&a[0][0],&a[0][1],&a[3][0],&a[3][1]); a[1][0]=a[3][0],a[1][1]=a[0][1]-1;a[2][0]=a[0][0]-1,a[2][1]=a[3][1]; a[0][0]--,a[0][1]--; memset(b,128,sizeof(b));gg=b[0][0]; shi=0; fo(i,1,n){ scanf("%d%d",&k,&l); fo(j,0,3)if(k<=a[j][0]&&l<=a[j][1])b[2*j][i]=k; fo(j,0,3)if(k<=a[j][0]&&l<=a[j][1])b[2*j+1][i]=l; } fo(j,0,7)build(j,1,1,n); for(scanf("%d",&m);m;m--){ scanf("%d",&k); if(k==1){ scanf("%d%d%d",&l,&r,&u); fo(j,0,3){ find(j*2,1,1,n,l,r,u); } } else if(k==2){ scanf("%d%d%d",&l,&r,&u); fo(j,0,3){ find(j*2+1,1,1,n,l,r,u); } } else{ scanf("%d%d",&l,&r); printf("%d\n",getans(1,1,n,l,r)); } } } //printf("%d\n",shi); }