差分

基础知识：一维差分数组的前缀和就是原序列。区间修改的时候，比如[l,r]每个元素+k的时候，差分数组只有两个值变化：b[l]+k，b[r+1]-k

797. 差分

题意：输出区间修改后的原序列
思路：贴个模板熟悉一下。

#include <iostream>
#include <algorithm>
#include <cstdio>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
using namespace std;
const int maxn=1e5+5;

int n,m,l,r,c;
//a是原序列，b是差分序列，ans是差分序列的前缀和，也就是修改后的最终序列
int a[maxn],b[maxn],ans[maxn];

int main()
{
	cin>>n>>m;
	rep(i,1,n)
	{
		cin>>a[i];
		b[i]=a[i]-a[i-1];
	}	
	rep(i,1,m)
	{
		cin>>l>>r>>c;
		b[l]+=c;
		b[r+1]-=c;
	} 
	rep(i,1,n)
	{
		ans[i]=ans[i-1]+b[i];
	}
	rep(i,1,n)
		cout<<ans[i]<<" ";
	cout<<endl;
	return 0;
}

但实际上，我们并不会说把差分序列直接算出来我们只会做一个标记。然后把原数组a[i]和差分数组b的前缀和相加，就可以得到最终的a[i]。然后就可以做最终的a数组的前缀和

#include <iostream>
#include <algorithm>
#include <cstdio>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
using namespace std;
const int maxn=1e5+5,INF=0x3f3f3f3f;

int n,m,l,r,c;
int a[maxn],b[maxn],pref[maxn];

int main()
{
	
    cin>>n>>m;
    rep(i,1,n)
    	cin>>a[i];
    while(m--)
    {
    	cin>>l>>r>>c;
    	b[l]+=c;
    	b[r+1]-=c;
	}
	int sum=0;
	for(int i=1;i<=n;++i)
	{
		sum+=b[i];
		pref[i]=pref[i-1]+a[i]+sum;
		a[i]+=sum;
	}
	
	rep(i,1,n)
		cout<<a[i]<<" ";
	cout<<"\n";
	
	rep(i,1,n)
		cout<<pref[i]<<" ";
	cout<<"\n";
	return 0;
}

798. 差分矩阵

题意：给定一个矩阵，对它做一些值的修改，求最终的矩阵
思路：和一维差分一样，在关键位置做修改，然后统计前缀和

#include <iostream>
#include <cstdio>
#define rep(i,a,b) for (int i=a; i<=b; ++i)
using namespace std;
const int maxn=1e3+5,INF=0x3f3f3f3f;
const int mod=1e9+7;

int n,m,q;
int x1,y1,x2,y2,c; 
int a[maxn][maxn],b[maxn][maxn];


int main()
{
	cin>>n>>m>>q;
	rep(i,1,n)
		rep(j,1,m)
			cin>>a[i][j];
	
	while(q--)
	{
		cin>>x1>>y1>>x2>>y2>>c;
		b[x1][y1]+=c;
		b[x2+1][y1]-=c;
		b[x1][y2+1]-=c;
		b[x2+1][y2+1]+=c;
		
	}
	
	//统计出差分的前缀和，然后a[i]加上相应的前缀和，就是最终的答案
	rep(i,1,n)
		rep(j,1,m)
			b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
	
	rep(i,1,n)
		rep(j,1,m)
			a[i][j]+=b[i][j];
	
	rep(i,1,n)
		rep(j,1,m)
			printf("%d%c",a[i][j],j==m?'\n':' ');
	return 0;
}

Monitor HDU - 6514

一道稍微有点难度的题

题意：给出n个监视器的监视范围，给定一些查询，问这些查询是否全部覆盖。
思路：覆盖设为1，不覆盖为0，查询的时候，看查询面积是否等于覆盖相等。因此要做二维前缀和。先标记差分数组，然后差分数组求前缀和，与原数组相加，得到变化后的数组。这里原数组全部为0。这里还要对得到的矩阵做去重，有值的地方全部设置为1，然后做前缀和。查询面积的时候，按照前缀和来给出面积是否相等。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e7+10;

int n,m,p,q,b[maxn];

void Add(int i,int j,int c)
{
	if(i>n||j>m)
		return;
	b[(i-1)*m+j]+=c;
}

int Query(int i,int j)
{
	if(i==0||j==0)
		return 0;
	return b[(i-1)*m+j];
}

int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		for(int i=0;i<=n*m;++i)
			b[i]=0;
		
		int x1,y1,x2,y2;
		scanf("%d",&p);
		while(p--)
		{
			scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			Add(x1,y1,1);
			Add(x1,y2+1,-1);
			Add(x2+1,y1,-1);
			Add(x2+1,y2+1,1);
		}
		
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				b[(i-1)*m+j]+=Query(i,j-1)+Query(i-1,j)-Query(i-1,j-1); 
		
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				if(b[(i-1)*m+j])
					b[(i-1)*m+j]=1;
							
		for(int i=1;i<=n;++i)
			for(int j=1;j<=m;++j)
				b[(i-1)*m+j]+=Query(i,j-1)+Query(i-1,j)-Query(i-1,j-1); 		
		
		
		scanf("%d",&q);
		while(q--)
		{
			scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
			int ret=Query(x2,y2)-Query(x1-1,y2)-Query(x2,y1-1)+Query(x1-1,y1-1);
			if(ret==(x2-x1+1)*(y2-y1+1))
				puts("YES");
			else
				puts("NO");
		}		
	} 
	return 0;
}