差分—基础数据结构 --- luogu P2484 [SDOI2011]打地鼠&&luogu P1083 借教室

题面传送门
首先明确,这是一道差分裸题,不要被它的蓝标签吓到。
算法简介:差分是一种和前缀和类似的数据结构,毕竟在差分过程中要进行前缀和,所以前缀和是差分的基础。差分能做到O(1)O(1)O(1)修改,但要O(n)O(n)O(n)查询,适用范围不如前缀和。差分适合查询极少,修改大大多于查询的题目。
算法实现: 首先我们定义差分数组s与基本数组a。
修改:我们要让x=5x=5x=5,y=9y=9y=9区间内加上z=5z=5z=5,那么我们有一个方法:fx+=z;fy+1=zf_x+=z;f_{y+1}-=zfx​+=z;fy+1​−=z;
0 0 0 0 5 0 0 0 0 0 -5 0 0 0
查询:那我们要查询x=5x=5x=5,y=9y=9y=9区间,怎么办呢?因为前缀和是差分的基础,所以先做一遍前缀和。
0 0 0 0 5 5 5 5 5 5 0 0 0 0
那么原数组就出来了。
那怎么查询呢?再做一遍前缀和呗!
0 0 0 0 5 10 15 20 25 25 25 25 25 25
再按照前缀和用ayax1=250=25a_y-a_{x-1}=25-0=25ay​−ax−1​=25−0=25即得答案。
按照前缀和的思路,二维差分怎么办?怎么修改x1=2x1=2x1=2,y1=5y1=5y1=5到x2=4x2=4x2=4,y2=7y2=7y2=7使其加上z=5z=5z=5?
首先根据套路,ax,ya_{x,y}ax,y​肯定要修改,那剩余怎么办?怎么推?
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
那先做一遍前缀和吧!
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 5 5 5 5 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0
做到这里时不对了,a2,8a_{2,8}a2,8​不应该有数值,所以在a2,8a_{2,8}a2,8​上放一个z-z−z。
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 5 0 0 0 0 0 0 0 0 0
又不对了,a5,5a_{5,5}a5,5​不应该有数值,所以还要在a5,5a_{5,5}a5,5​上放一个z-z−z
0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 5 5 5 0 0 0 0 0 0 0
0 0 0 0 0 0 0 -5 0 0 0 0 0 0
a5,8a_{5,8}a5,8​不应该有负数啊,所以亡羊补牢地在a5,8a_{5,8}a5,8​补上一个zzz。
所以二维差分修改就是:
ax1,y1+=za_{x1,y1}+=zax1,y1​+=z
ax1,y2+1=za_{x1,y2+1}-=zax1,y2+1​−=z
ax2+1,y1=za_{x2+1,y1}=zax2+1,y1​=z
ax2+1,y2+1+=za_{x2+1,y2+1}+=zax2+1,y2+1​+=z
有感觉和前缀和有点相似。
两个基础数据结构都指向了同一个数学模型:韦恩图!
那么对于这道题,只要枚举锤子的长和宽再枚举每一个点进行二维差分就好了。
个人理解: 差分数组的修改是个很好的方法,但它的代价是复杂的查询。若有其他东西来维护差分数组的查询就很好了。
代码实现:

#include<cstdio>
#include<cstring>
using namespace std;
int n,m,a[239][239],b[239][239];
int main(){
    register int i,j,x,y,l,r,ans=0,tot,flag;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++) scanf("%d",&a[i][j]),ans+=a[i][j];
    }
    for(i=n;i>=1;i--){
        for(j=m;j>=1;j--){
            if(ans%i==0&&ans%j==0){
                flag=0;
                memset(b,0,sizeof(b));
                for(x=1;x<=n;x++){
                    for(y=1;y<=m;y++){
                        b[x][y]+=b[x-1][y]+b[x][y-1]-b[x-1][y-1];
                        if(a[x][y]<b[x][y]){flag=1;break;}
                        b[x+i][y]-=a[x][y]-b[x][y];
                        b[x][y+j]-=a[x][y]-b[x][y];
                        b[x+i][y+j]+=a[x][y]-b[x][y];
                        b[x][y]=a[x][y];
                    }
                    if(flag) break;
                }
                if(!flag){
                    printf("%d",ans/i/j);
                    return 0;
                }
            }
        }
    }
}

题面传送门
这道题是提高组原题,可以用线段树维护区间中是否有少于000的数字,而且思路更简单,但对于差分数组的进一步了解还是很有帮助的。
对于这道题,用二分分出哪一个订单不满足要求,并用差分数组验证,最后是一遍查询。时间复杂度O(nlog2n)O(nlog^2n)O(nlog2n)

#include<bits/stdc++.h>
using namespace  std;
int n,m,s[1000001],d[1000001],q[1000001],a[1000001],b[1000001],c[1000001],l,r,mid,flag;
int main() {
	//freopen("1.in","r",stdin);
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;i++) scanf("%d",&s[i]);
	for(register int i=1;i<=m;i++)scanf("%d%d%d",&a[i],&b[i],&c[i]);
	l=0,r=m+1;
	while(l+1<r){
		flag=0;
		memset(d,0,sizeof(d));
		mid=(l+r)>>1;
		for(register int i=1;i<=mid;i++) d[b[i]]+=a[i],d[c[i]+1]-=a[i];
		for(register int i=1;i<=n;i++){
			d[i]+=d[i-1];
			if(d[i]>s[i]){flag=1;break;}
		}
		if(flag) r=mid;
		else l=mid;
	}
	if(l==m) printf("0");
	else printf("-1\n%d",r);
	return 0;
}
上一篇:【第766期】你不懂JS:对象


下一篇:SpringBoot笔记十四:消息队列