ACwing ： 798. 差分矩阵

2021-05-17 11:30

阅读：635

标签：没有行修改元素 int 位置 ott its printf back

不得不说之前的差分我真的是掌握的不好。。

一维差分确实简单一看就会，但是学会了之后却并不能灵活的运用。

而二维的差分我甚至还琢磨了很长时间

懒得画图所以没有图。。
对于二维差分的定义，百度百科是这么说的

顾名思义，就是在矩阵中，一行（一列）的元素与上一行（上一列）对应元素的差值，依次排列在上一行（上一列）元素对应所在位置。

（好像说的是矩阵差分，但是问题不大）

但是只要你用模板代码打出一个差分数组就会发现这个数组的排列并不规律，换句话说我并没有看懂这个。。

因此我们完全可以忽略差分数组一个点的意义

只需要抓住其前缀和是原来数值的特点进行修改即可

而每次更新时都可以将其拆解为两个一维的数组去处理

#include#define R register int
using namespace std;
const int maxn=1002;
int m,n,q;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch‘0‘||ch>‘9‘) if(ch==‘-‘) f=-1,ch=getchar();
    while(ch>=‘0‘&&ch‘9‘) x=(x3)+(x1)+ch-‘0‘,ch=getchar();
    return x*f;
}int a[maxn][maxn];
inline void insert(int x1,int y1,int x2,int y2,int v)
{
    a[x1][y1]+=v;
    a[x2+1][y1]-=v;
    a[x1][y2+1]-=v;
    a[x2+1][y2+1]+=v;
}

int main()
{
    int i,j;
    n=read();m=read();q=read();
    for( i=1;i)
    for( j=1;j)
    {
        int x=read();
        insert(i,j,i,j,x);
    }
    for( i=1;i)
    {
        int x1=read(),y1=read(),x2=read(),y2=read(),c=read();
        insert(x1,y1,x2,y2,c);
    }
    for(i=1;i)
     for( j=1;j)
      a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
    for( i=1;i)
    {
        for( j=1;j)
        printf("%d ",a[i][j]);
        puts("");
    }
    return 0;
}

ACwing ： 798. 差分矩阵

标签：没有行修改元素 int 位置 ott its printf back

原文地址：https://www.cnblogs.com/smartljy/p/11777466.html

上一篇：Prometheus（二）：Prometheus 监控Windows机器

下一篇：设置API：wx.openSetting,wx.getSetting使用说明(示例：地图授权与取消授权后的重新授权)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：ACwing ： 798. 差分矩阵
文章链接：http://soscw.com/index.php/essay/86699.html

亲，登录后才可以留言！

ACwing ： 798. 差分矩阵

评论

热门文章

推荐文章

最新文章

置顶文章