Description
火神最爱的就是吃鱼了，所以某一天他来到了一个池塘边捕鱼。池塘可以看成一个二维的平面，而他的渔网可以看成一个与坐标轴平行的矩形。 池塘里的鱼不停地在水中游动，可以看成一些点。有的时候会有鱼游进渔网，有的时候也会有鱼游出渔网。所以火神不知道什么时候收网才可以抓住最多的鱼，现在他寻求你的帮助。 他对池塘里的每条鱼都给予了一个标号，分别从1到n标号，n表示池塘里鱼的总数。鱼的游动可以概括为两个动作： 1 l r d : 表示标号在[l，r]这个区间内的鱼向x轴正方向游动了d个单位长度。 2 l r d：表示标号在[l，r]这个区间内的鱼向y轴正方向游动了d个单位长度。 在某些时刻火神会询问你现在有多少条他关心的鱼在渔网内(边界上的也算)，请你来帮助他吧。
第一行包含一个整数T，表示测试数据组数。 对于每组测试数据： 第一行包含一个整数n表示鱼的总数。 第二行包含四个整数x1,y1,x2,y2，表示渔网的左下角坐标和右上角坐标。 接下来n行每行两个整数xi,yi，表示标号为i的鱼初始时刻的坐标。 接下来一行包含一个整数m，表示后面的事件数目。 接下来的mm行每行为以下三种类型的一种： 1 l r d : 表示标号在[l，r]这个区间内的鱼向x轴正方向游动了d个单位长度。 2 l r d：表示标号在[l，r]这个区间内的鱼向y轴正方向游动了d个单位长度。 3 l r : 表示询问现在标号在[l，r]这个区间内的鱼有多少在渔网内。
Output
对于每组数据的每个询问，输出一个整数表示对应的答案。
1 5 1 1 5 5 1 1 2 2 3 3 4 4 5 5 3 3 1 5 1 2 4 2 3 1 5
Sample Output
5 4
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
有一个重要条件：游动的距离是正数，意味着一条鱼最多是从外面游进网里然后再游出去，而网是不会动的，那就分别维护每条鱼的横坐标和纵坐标是否在网内，并维护答案即可 只讨论x轴，Y轴是一样的。 维护在第一条线的左边mi和第二条线的左边ma的最大值，每次操作后如果mi>x1或ma>x2那就非法了，然后去修改并维护答案，在维护答案的时候注意，如果x坐标是合法的，那还要判断y坐标也是合法的。 打的时候所有关于线段树的东西都复制一遍就行了 码农是必须的了
Code
using namespace std;
int ac,n;
ll an,x1,y1,x2,y2,a[N][
3];
struct note{
ll l,mi,
ma;
};
note t[N
*50],t1[N
*50];
ll ans[N
*50];
ll max(ll a,ll b){
return a>b?a:b;}
void build(
int v,
int i,
int j)
{
if(i==j)
{
t[v].mi=t[v].
ma=INF;t[v].l=
0;
if(a[i][
1]<=x2)
if(a[i][
1]<x1) t[v].mi=a[i][
1];
else t[v].
ma=a[i][
1];
t1[v].mi=t1[v].
ma=INF;t1[v].l=
0;
if(a[i][
2]<=y2)
if(a[i][
2]<y1) t1[v].mi=a[i][
2];
else t1[v].
ma=a[i][
2];
if(a[i][
1]>=x1&&a[i][
2]>=y1&&a[i][
1]<=x2&&a[i][
2]<=y2) ans[v]=
1;
else ans[v]=
0;
return;
}
int m=(i+j)/
2;build(v
*2,i,
m);build(v
*2+
1,
m+
1,j);ans[v]=ans[v
*2]+ans[v
*2+
1];
t[v].mi=max(t[v
*2].mi,t[v
*2+
1].mi);t[v].
ma=max(t[v
*2].
ma,t[v
*2+
1].
ma);t[v].l=t1[v].l=
0;
t1[v].mi=max(t1[v
*2].mi,t1[v
*2+
1].mi);t1[v].
ma=max(t1[v
*2].
ma,t1[v
*2+
1].
ma);
}
void down(
int v)
{
ll l=t[v].l;
if(l==
0)
return;
t[v
*2].mi+=l;t[v
*2+
1].mi+=l;t[v
*2].
ma+=l;t[v
*2+
1].
ma+=l;t[v
*2].l+=l;t[v
*2+
1].l+=l;t[v].l=
0;
}
void down1(
int v)
{
ll l=t1[v].l;
if(l==
0)
return;
t1[v
*2].mi+=l;t1[v
*2+
1].mi+=l;t1[v
*2].
ma+=l;t1[v
*2+
1].
ma+=l;t1[v
*2].l+=l;t1[v
*2+
1].l+=l;t1[v].l=
0;
}
void changx(
int v,
int i,
int j,
int x,
int y,ll z)
{
if(i==
x&&j==
y){t[v].l+=z;t[v].mi+=z;t[v].
ma+=z;
return;}
int m=(i+j)/
2;down(v);
if(
y<=
m) changx(v
*2,i,
m,
x,
y,z);
else if(
x>
m) changx(v
*2+
1,
m+
1,j,
x,
y,z);
else changx(v
*2,i,
m,
x,
m,z),changx(v
*2+
1,
m+
1,j,
m+
1,
y,z);ans[v]=ans[v
*2]+ans[v
*2+
1];
t[v].mi=max(t[v
*2].mi,t[v
*2+
1].mi);t[v].
ma=max(t[v
*2].
ma,t[v
*2+
1].
ma);
}
void changy(
int v,
int i,
int j,
int x,
int y,ll z)
{
if(i==
x&&j==
y){t1[v].l+=z;t1[v].mi+=z;t1[v].
ma+=z;
return;}
int m=(i+j)/
2;down1(v);
if(
y<=
m) changy(v
*2,i,
m,
x,
y,z);
else if(
x>
m) changy(v
*2+
1,
m+
1,j,
x,
y,z);
else changy(v
*2,i,
m,
x,
m,z),changy(v
*2+
1,
m+
1,j,
m+
1,
y,z);ans[v]=ans[v
*2]+ans[v
*2+
1];
t1[v].mi=max(t1[v
*2].mi,t1[v
*2+
1].mi);t1[v].
ma=max(t1[v
*2].
ma,t1[v
*2+
1].
ma);
}
void find1(
int v,
int i,
int j)
{
if(i==j){
if(t1[v].
ma>=y1&&t1[v].
ma<=y2) ans[v]=
1;
else ans[v]=
0;t[v].
ma=t[v].mi;t[v].mi=INF;
return;}
int m=(i+j)/
2;down(v);down1(v);
if(t[v
*2].mi>=x1) find1(v
*2,i,
m);
else find1(v
*2+
1,
m+
1,j);ans[v]=ans[v
*2]+ans[v
*2+
1];
t[v].mi=max(t[v
*2].mi,t[v
*2+
1].mi);t[v].
ma=max(t[v
*2].
ma,t[v
*2+
1].
ma);
t1[v].mi=max(t1[v
*2].mi,t1[v
*2+
1].mi);t1[v].
ma=max(t1[v
*2].
ma,t1[v
*2+
1].
ma);
}
void find2(
int v,
int i,
int j)
{
if(i==j){ans[v]=
0;t1[v].mi=t1[v].
ma=t[v].mi=t[v].
ma=INF;
return;}
int m=(i+j)/
2;down(v);down1(v);
if(t[v
*2].
ma>x2) find2(v
*2,i,
m);
else find2(v
*2+
1,
m+
1,j);ans[v]=ans[v
*2]+ans[v
*2+
1];
t[v].mi=max(t[v
*2].mi,t[v
*2+
1].mi);t[v].
ma=max(t[v
*2].
ma,t[v
*2+
1].
ma);
t1[v].mi=max(t1[v
*2].mi,t1[v
*2+
1].mi);t1[v].
ma=max(t1[v
*2].
ma,t1[v
*2+
1].
ma);
}
void find3(
int v,
int i,
int j)
{
if(i==j){
if(t[v].
ma>=x1&&t[v].
ma<=x2) ans[v]=
1;
else ans[v]=
0;t1[v].
ma=t1[v].mi;t1[v].mi=INF;
return;}
int m=(i+j)/
2;down1(v);down(v);
if(t1[v
*2].mi>=y1) find3(v
*2,i,
m);
else find3(v
*2+
1,
m+
1,j);ans[v]=ans[v
*2]+ans[v
*2+
1];
t[v].mi=max(t[v
*2].mi,t[v
*2+
1].mi);t[v].
ma=max(t[v
*2].
ma,t[v
*2+
1].
ma);
t1[v].mi=max(t1[v
*2].mi,t1[v
*2+
1].mi);t1[v].
ma=max(t1[v
*2].
ma,t1[v
*2+
1].
ma);
}
void find4(
int v,
int i,
int j)
{
if(i==j){ans[v]=
0;t1[v].mi=t1[v].
ma=t[v].mi=t[v].
ma=INF;
return;}
int m=(i+j)/
2;down1(v);down(v);
if(t1[v
*2].
ma>y2) find4(v
*2,i,
m);
else find4(v
*2+
1,
m+
1,j);ans[v]=ans[v
*2]+ans[v
*2+
1];
t[v].mi=max(t[v
*2].mi,t[v
*2+
1].mi);t[v].
ma=max(t[v
*2].
ma,t[v
*2+
1].
ma);
t1[v].mi=max(t1[v
*2].mi,t1[v
*2+
1].mi);t1[v].
ma=max(t1[v
*2].
ma,t1[v
*2+
1].
ma);
}
void get(
int v,
int i,
int j,
int x,
int y)
{
if(i==
x&&j==
y) {an+=ans[v];
return;}
int m=(i+j)/
2;
if(
y<=
m) get(v
*2,i,
m,
x,
y);
else if(
x>
m) get(v
*2+
1,
m+
1,j,
x,
y);
else get(v
*2,i,
m,
x,
m),get(v
*2+
1,
m+
1,j,
m+
1,
y);
}
int main()
{
for(scanf(
"%d",&ac);ac;ac--)
{
scanf(
"%d",&n);scanf(
"%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
fo(i,
1,n)
{
ll
x,
y;scanf(
"%lld%lld",&
x,&
y);
a[i][
1]=
x;a[i][
2]=
y;
}
memset(t,
0,sizeof(t));memset(t1,
0,sizeof(t1));build(
1,
1,n);
int m;
for(scanf(
"%d",&
m);
m;
m--)
{
int ta;scanf(
"%d",&ta);
if(ta==
1)
{
int x,
y;ll z;scanf(
"%d%d%lld",&
x,&
y,&z);
changx(
1,
1,n,
x,
y,z);
while(t[
1].mi>=x1) find1(
1,
1,n);
while(t[
1].
ma>x2) find2(
1,
1,n);
}
if(ta==
2)
{
int x,
y;ll z;scanf(
"%d%d%lld",&
x,&
y,&z);
changy(
1,
1,n,
x,
y,z);
while(t1[
1].mi>=y1) find3(
1,
1,n);
while(t1[
1].
ma>y2) find4(
1,
1,n);
}
if(ta==
3)
{
int x,
y;scanf(
"%d%d",&
x,&
y);
an=
0;get(
1,
1,n,
x,
y);
printf(
"%lld\n",an);
}
}
}
}
转载请注明原文地址: https://ju.6miu.com/read-1302568.html
