差分

P3397 地毯

syoj 1829. 地毯

二维差分板子。

#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;
} 

P8666 [蓝桥杯 2018 省 A] 三体攻击

syoj 1830. 三体攻击

三维差分的板子。写法类比二维。

#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;
}