Description

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

Solution

先把题目的两个维度拆开来分析， 每个数在变化的过程中，只会不停的增加，也就是每个点最多只会进一次区间，出一次区间， 所有每个点进入区间和出区间的操作可以一个一个来做， 用线段树，线段树内存mi,mi1,分别表示 x<X1 的最大的x值以及位置，ma,ma1表示 x<X2 的最大的x以及位置，（注意，一个点可能即是ma也是mi） y也开一颗差不多的， 同时还要记录一下当前区间x,y都合法的个数（答案）， mi,mi1的初始值为-maxlongint， 预处理时，如果一个点的x,y其中一个越过了合法的区间，很显然这个点就没有用了，它的mi,ma就没有值， 每次区间修改x，ma就有可能>X2，这样就不合法所以，因此我们要找到是哪个不合法，然后把它同时在两颗树中删掉，也有可能mi>X1，把它从mi中删掉，同时看一下它的x,y是否合法，合法就加进s，如果有很多都要做操作，则一个一个来， 修改y一样，

复杂度： O(nlog(n))

Code

#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) #define OK(q,w) (X1<=(q)&&(q)<=X2&&Y1<=(w)&&(w)<=Y2) #define B b[E] using namespace std; const int N=30500,INF=2147483640; int read(int &n) { char ch=' ';int q=0,w=1; for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar()); if(ch=='-')w=-1,ch=getchar(); for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n; } int m,n,ans,X1,Y1,X2,Y2; struct qwqw{int x,y;}a[N]; struct qqww{int i,i1,a,a1,s,la;}b[2][3*N]; void merge(int q,int w,int e) { fo(E,0,1) { B[q]=B[w]; B[q].s=B[w].s+B[e].s; if(B[q].i<B[e].i)B[q].i=B[e].i,B[q].i1=B[e].i1; if(B[q].a<B[e].a)B[q].a=B[e].a,B[q].a1=B[e].a1; } } void doit(int l,int r,int e) { fo(E,0,1)if(B[e].la) { if(B[e].i!=-INF)B[e].i+=B[e].la; B[e].a+=B[e].la; if(l!=r)B[e*2].la+=B[e].la,B[e*2+1].la+=B[e].la; B[e].la=0; } } void build(int l,int r,int e) { if(l==r) { if(a[l].x<=X2&&a[l].y<=Y2) { b[0][e].a=a[l].x,b[1][e].a=a[l].y; b[0][e].a1=b[1][e].a1=l; if(OK(b[0][e].a,b[1][e].a))b[0][e].s=1; if(a[l].x<X1)b[0][e].i=a[l].x,b[0][e].i1=l; if(a[l].y<Y1)b[1][e].i=a[l].y,b[1][e].i1=l; } return; } int mid=(l+r)/2; build(l,mid,e*2),build(mid+1,r,e*2+1); merge(e,e*2,e*2+1); } void change(int l,int r,int e,int E,int l1,int r1,int l2) { if(l==l1&&r==r1){B[e].la+=l2;doit(l,r,e); return;} int mid=(l+r)/2; doit(l,mid,e*2),doit(mid+1,r,e*2+1); if(r1<=mid)change(l,mid,e*2,E,l1,r1,l2); else if(mid<l1)change(mid+1,r,e*2+1,E,l1,r1,l2); else change(l,mid,e*2,E,l1,mid,l2),change(mid+1,r,e*2+1,E,mid+1,r1,l2); merge(e,e*2,e*2+1); } void delt(int l,int r,int e,int l2) { if(l==r){b[0][e]=b[1][e]=b[0][0];return;} int mid=(l+r)/2; doit(l,mid,e*2),doit(mid+1,r,e*2+1); if(l2<=mid)delt(l,mid,e*2,l2); else delt(mid+1,r,e*2+1,l2); merge(e,e*2,e*2+1); } void join(int l,int r,int e,int l2) { if(l==r) { if(OK(b[0][e].a,b[1][e].a))b[0][e].s=1; if(b[0][1].i>=X1)b[0][e].i=-INF,b[0][e].i1=0; if(b[1][1].i>=Y1)b[1][e].i=-INF,b[1][e].i1=0; return; } int mid=(l+r)/2; doit(l,mid,e*2),doit(mid+1,r,e*2+1); if(l2<=mid)join(l,mid,e*2,l2); else join(mid+1,r,e*2+1,l2); merge(e,e*2,e*2+1); } int find(int l,int r,int e,int l1,int r1) { if(l==l1&&r==r1)return b[0][e].s; int mid=(l+r)/2; doit(l,mid,e*2),doit(mid+1,r,e*2+1); if(r1<=mid)return find(l,mid,e*2,l1,r1); else if(mid<l1)return find(mid+1,r,e*2+1,l1,r1); else return find(l,mid,e*2,l1,mid)+find(mid+1,r,e*2+1,mid+1,r1); } int main() { int q,w,_,l,r; b[0][0].i=-INF,b[0][0].a=-INF; fo(i,1,3*N-10)fo(j,0,1)b[j][i]=b[0][0]; read(_); while(_--) { read(n); read(X1),read(Y1),read(X2),read(Y2); fo(i,1,n)read(a[i].x),read(a[i].y); build(1,n,1); read(m); fo(i,1,m) { read(q),read(l),read(r); if(q==1) { read(w); change(1,n,1,0,l,r,w); while(b[0][1].a>X2)delt(1,n,1,b[0][1].a1); while(b[0][1].i>=X1) join(1,n,1,b[0][1].i1); } if(q==2) { read(w); change(1,n,1,1,l,r,w); while(b[1][1].a>Y2)delt(1,n,1,b[1][1].a1); while(b[1][1].i>=Y1)join(1,n,1,b[1][1].i1); } if(q==3)printf("%d\n",find(1,n,1,l,r)); } fo(i,1,3*n)fo(j,0,1)b[j][i]=b[0][0]; } return 0; }