扫描二维码
随时随地手机看文章
目标,掌握差分的概念、和解题的思路
差分就是前缀和的逆过程!!!
一维差分
什么是一维差分?
那么差分可以用来干嘛呢?
让我们来看这样一个操作
通过差分,我们可以快速对前缀和数组的一个区间的数进去操作
再思考,如何构建差分呢??需要构建嘛
题目
输入一个长度为n的整数序列。
接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。
请你输出进行完所有操作后的序列。
题解
这里需要注意:我们构造差分的方法是insert(i,i,s[i]);
通过插入的方法我们自然而然的就可以得到差分了
模板
a是s的差分,想要对s[l,r]中的一系列数操作
a[l] += val;
a[r+1] -= val;
二维差分
和前缀和类似,我们也有二位差分,就是对一个前缀和的矩阵中一系列数操作
题目
输入一个n行m列的整数矩阵,再输入q个操作,每个操作包含五个整数x1, y1, x2, y2, c,其中(x1, y1)和(x2, y2)表示一个子矩阵的左上角坐标和右下角坐标。
每个操作都要将选中的子矩阵中的每个元素的值加上c。
请你将进行完所有操作后的矩阵输出。
思路还是一样,用差分来做
题解
注意:这里输出的时候用的是BufferWrite()
当要输出大量数据的时候可以使用bw,可以有效节省时间
还有要记得关闭资源哦!!!
模板
public static void insert(int x1, int y1, int x2, int y2, int val){
a[x1][y1] += val;
a[x1][y2+1] -= val;
a[x2+1][y1] -= val;
a[x2+1][y2+1] += val;
}
Oct. 20, 2022 ---- 全球市场研究机构TrendForce集邦咨询公告「2023年集邦拓墣科技产业大预测」,精彩内容节录如下:
关键字: TrendForce集邦咨询 拓墣科技Oct. 19, 2022 ---- 根据TrendForce集邦咨询调查显示,2022年第三季全球电视出货量达5,139万台,季增12.4%,年减2.1%,是自2014年以来同季出货最低纪录。由于全球仍持续垄罩在高通胀...
关键字: TrendForce集邦咨询 OLEDOct. 18, 2022 ---- 根据TrendForce集邦咨询最新调查表示,疫情后紧张的物料情况已于今年下半年改善,短料的供货交期显著恢复。然而在物料供给无虞,需求可被满足的情况下,2023年的服务器整机出货量年...
关键字: TrendForce集邦咨询 服务器