本文共 2311 字，大约阅读时间需要 7 分钟。
题目大意
池塘里有一些鱼和一个渔网，池塘可以看成一个二维的平面，而渔网可以看成一个与坐标轴平行的矩形。每条鱼都被给予了一个标号，分别从 1 到 n 标号， n 表示池塘里鱼的总数。鱼的游动可以概括为两个动作：
1 l r d : 表示标号在[ l ， r ]这个区间内的鱼向 x 轴正方向游动了 d 个单位长度。
2 l r d ：表示标号在[ l ， r ]这个区间内的鱼向 y 轴正方向游动了 d 个单位长度。
还有询问操作： 3 l r 表示询问现在标号在[ l ， r ]这个区间内的鱼有多少在渔网内。
输入格式
第一行包含一个整数 T ，表示测试数据组数。
对于每组测试数据：
第一行包含一个整数 n 表示鱼的总数。
第二行包含四个整数 x1 , y1 , x2 , y2 ，表示渔网的左下角坐标和右上角坐标。
接下来 n 行每行两个整数 xi , yi ，表示标号为i的鱼初始时刻的坐标。
接下来一行包含一个整数 m ，表示后面的事件数目。
接下来的 m 行每行为以下三种类型的一种：
1 l r d : 表示标号在[ l ， r ]这个区间内的鱼向 x 轴正方向游动了 d 个单位长度。
2 l r d ：表示标号在[ l ， r ]这个区间内的鱼向 y 轴正方向游动了 d 个单位长度。
3 l r : 表示询问现在标号在[ l ， r ]这个区间内的鱼有多少在渔网内。
输出格式
对于每组数据的每个询问，输出一个整数表示对应的答案。
数据范围
对于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]范围内。
/*hdu 5283用鱼的编号为下标建立线段树，每一个节点维护当前区间内小于x1（y1）的最大x（y）值和小于x2（y2）点最大x（y）的值。因为鱼的运动方向具有单调性，所以一个鱼一但出去了就再也回不来了 ，那么久删除这些节点，不断更行1号节点的值。注意x，y各开一棵线段树。*/#include #include #include #include #include #include #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)//x,x<<1,x<<1|1{ fo(E,0,1) { B[q]=B[w]; B[q].s=B[w].s+B[e].s; if(B[q].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 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;}
转载地址：http://crqji.baihongyu.com/