二维差分板子。
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int a[N][N],s[N][N];
int main(){
scanf("%d%d",&n,&m);
while(m--){
int x,y,xx,yy;
scanf("%d%d%d%d",&x,&y,&xx,&yy);
a[x][y]++;
a[xx+1][yy+1]++;
a[x][yy+1]--;
a[xx+1][y]--;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
printf("%d ",a[i][j]);
}
puts("");
}
return 0;
}
三维差分的板子。写法类比二维。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int A,B,C,m;
int ans;
int s[N],d[N];
int la[N],ra[N],lb[N],rb[N],lc[N],rc[N],h[N];
int p(int i,int j,int k){
if(i>A||j>B||k>C)return 0;
return ((i-1)*B+j-1)*C+k;
}
void add(int i,int j,int k,int d){s[p(i,j,k)]+=d;}
bool check(int x){
memset(s,0,sizeof s);
for(int i=1;i<=x;i++){
int q=h[i];
add(la[i],lb[i],lc[i],q);
add(ra[i]+1,rb[i]+1,lc[i],q);
add(ra[i]+1,lb[i],rc[i]+1,q);
add(la[i],rb[i]+1,rc[i]+1,q);
add(ra[i]+1,lb[i],lc[i],-q);
add(la[i],rb[i]+1,lc[i],-q);
add(la[i],lb[i],rc[i]+1,-q);
add(ra[i]+1,rb[i]+1,rc[i]+1,-q);
}
for(int i=1;i<=A;i++)
for(int j=1;j<=B;j++)
for(int k=1;k<=C;k++) add(i+1,j,k,s[p(i,j,k)]);
for(int i=1;i<=A;i++)
for(int j=1;j<=B;j++)
for(int k=1;k<=C;k++) add(i,j+1,k,s[p(i,j,k)]);
for(int i=1;i<=A;i++)
for(int j=1;j<=B;j++)
for(int k=1;k<=C;k++) add(i,j,k+1,s[p(i,j,k)]);
for(int i=1;i<=A*B*C;i++) if(s[i]>d[i]) return 1;
return 0;
}
int main(){
scanf("%d%d%d%d",&A,&B,&C,&m);
for(int i=1;i<=A*B*C;i++) scanf("%d",&d[i]);
for(int i=1;i<=m;i++) scanf("%d%d%d%d%d%d%d",&la[i],&ra[i],&lb[i],&rb[i],&lc[i],&rc[i],&h[i]);
int l=1,r=m;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
r=mid-1;
ans=mid;
}
else l=mid+1;
}
printf("%d",ans);
return 0;
}