Description
- W*H ≤ 2500000 , N,Q ≤ 200000
Solution
- 不难发现一滴墨水的影响范围是一个正方形
- 最中间的X是a，之后每往外一层就减b，知道a%b
- 先将a%b的影响单独取出来。
- 剩下若干层，从外到里分别是b,2b,3b,…,kb
- 考虑每一层的矩形分别加b即可成为这个“回”字型的影响图。
b b b b b
b 2b 2b 2b b
b 2b 3b 2b b
b 2b 2b 2b b
b b b b b
-
将每一层分别加b，根据二维前缀和的方法即可快速加一个矩形
(+b)-------- (-b)
|***************|
(-b)---------(+b) -
多层加在一起会变成
b 0 0 0 0 0 0 -b
0 b 0 0 0 0 -b 0
0 0 b 0 0 -b 0 0
0 0 0 b -b 0 0 0
0 0 0 -b b 0 0 0
0 0 -b 0 0 b 0 0
0 -b 0 0 0 0 b 0
-b 0 0 0 0 0 0 b -
将左上到右下和右上到左下的对角线分别计算。一段对角线的+b或-b依旧用差分区间修改。
-
这样通过对角线的差分还原出上图，再通过二维前缀和即可还原出每一个位置。然后再用前缀和就可以实现O(1)查询。
-
现在我们考虑一下出界的情况（即对角线有一部分在边界外时），这也是这题最为坑且难打的地方。
-
-
例如红色的对角线上要全部+b
-
但是出界的那一些显然不能找到地方填。
-
所以我们考虑这些+b都是对右下的造成影响，所以出界的那一段就等价于橙色的那一段。
-
所以将出界的部分影射到边界上后区间修改即可（又有一个差分）
-
其它四个角以及出的不同的界要讨论一波，以此类推。
-
最后复杂度O(w*h)
-
PS：注意一下精度（
鬼知道为什么出题人还要求平均数，难道是专门卡精度的？）
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#define maxm 2500005
#define maxn 200005
#define ll long long
using namespace std;
int w,h,q,n,i,j,k,x,y,a,b,d,xx,yy,t;
ll sum[maxm],level[maxm],pos[maxm],neg[maxm],row[maxm],col[maxm],cnt,ret;
int I(int x,int y){
if (x<1||y<1||x>w||y>h) return 0; else
return (x-1)*h+y;
}
void add(int x,int y,int d){
if (x<=w&&y<=h)
level[I(max(x,1),max(y,1))]+=d;
}
int main(){
freopen("rezero07.in","r",stdin);
freopen("ceshi.out","w",stdout);
// freopen("ceshi.in","r",stdin);
scanf("%d%d",&w,&h);
scanf("%d",&n);
for(i=1;i<=n;i++) {
scanf("%d%d%d%d",&x,&y,&a,&b);
d=a/b-1;
add(x-d-1,y-d-1,a%b),add(x+d+2,y+d+2,a%b);
add(x-d-1,y+d+2,-a%b),add(x+d+2,y-d-1,-a%b);
//左上
xx=x-d,yy=y-d;
if (xx<1&&yy<1) {
t=min(1-xx,1-yy);
level[I(1,1)]+=t*b,xx+=t,yy+=t;
}
if (xx<1) {
t=1-xx;
row[I(1,yy)]+=b,row[I(1,yy+t)]-=b;
xx+=t,yy+=t;
}
if (yy<1) {
t=1-yy;
col[I(xx,1)]+=b,col[I(xx+t,1)]-=b;
xx+=t,yy+=t;
}
pos[I(xx,yy)]+=b;
// continue;
//右下
xx=x+d+2,yy=y+d+2;
if (xx<=w&&yy<=h) pos[I(xx,yy)]-=b;
// continue;
//左下
xx=x+d+1,yy=y-d;
if (xx>w&&y<1) {
t=min(xx-w,1-yy);
xx-=t,yy+=t;
}
if (xx>w) {
t=xx-w;
xx-=t,yy+=t;
}
if (yy<1) {
t=1-yy;
col[I(xx-t+1,1)]-=b;
if (xx+1<=w) col[I(xx+1,1)]+=b;
xx-=t,yy+=t;
}
neg[I(xx,yy)]-=b;
//右上
xx=x-d-1,yy=y+d+2;
if (xx>=1&&yy<=h) neg[I(xx,yy)]+=b;
else xx++,yy--;
if (xx<1&&yy>h) {
t=min(1-xx,yy-h);
xx+=t,yy-=t;
}
if (xx<1) {
t=1-xx;
row[I(1,yy-t+1)]-=b;
if (yy+1<=h) row[I(1,yy+1)]+=b;
xx+=t,yy-=t;
}
if (yy>h) {
t=yy-h;
xx+=t,yy-=t;
}
}
for(i=1;i<=w;i++) for(cnt=0,j=1;j<=h;j++)
cnt+=row[I(i,j)],level[I(i,j)]+=cnt;
for(j=1;j<=h;j++) for(cnt=0,i=1;i<=w;i++)
cnt+=col[I(i,j)],level[I(i,j)]+=cnt;
for(x=1,y=1;y<=h;y++) for(cnt=0,i=x,j=y;i<=w&&j<=h;i++,j++)
cnt+=pos[I(i,j)],level[I(i,j)]+=cnt;
for(x=2,y=1;x<=w;x++) for(cnt=0,i=x,j=y;i<=w&&j<=h;i++,j++)
cnt+=pos[I(i,j)],level[I(i,j)]+=cnt;
for(x=1,y=1;x<=w;x++) for(cnt=0,i=x,j=y;i>=1&&j<=h;i--,j++)
cnt+=neg[I(i,j)],level[I(i,j)]+=cnt;
for(x=w,y=2;y<=h;y++) for(cnt=0,i=x,j=y;i>=1&&j<=h;i--,j++)
cnt+=neg[I(i,j)],level[I(i,j)]+=cnt;
for(i=1;i<=w;i++) for(j=1;j<=h;j++)
level[I(i,j)]+=level[I(i-1,j)]+level[I(i,j-1)]-level[I(i-1,j-1)];
for(i=1;i<=w;i++) for(j=1;j<=h;j++)
sum[I(i,j)]=level[I(i,j)]+sum[I(i-1,j)]+sum[I(i,j-1)]-sum[I(i-1,j-1)];
scanf("%d",&q);
while (q--) {
scanf("%d%d%d%d",&x,&y,&i,&j);
ll ans=sum[I(i,j)]-sum[I(x-1,j)]-sum[I(i,y-1)]+sum[I(x-1,y-1)];
ll s=(i-x+1)*(j-y+1);
ll ret=ans/s;
if ((ans%s)*2>=s) ret++;
printf("%lld
",ret);
}
}