ToB企服应用市场:ToB评测及商务社交产业平台

标题: 二维差分·学习备忘录 [打印本页]

作者: 王國慶 时间: 2024-8-12 19:56
标题: 二维差分·学习备忘录
二维差分

为什么我为OI泪目？因为我菜得离谱......

引入

一维差分用来O(1)修改区间，配合上一维前缀和就是O(N)的查询区间和。
差分为前缀和的逆运算。
二维差分同理。
接下来这道题就用二维差分来解决。
\(例题：地毯>>\)

地毯

标题描述

在 \(n\times n\) 的格子上有 \(m\) 个地毯。
给出这些地毯的信息，问每个点被多少个地毯覆盖。
输入格式

第一行，两个正整数 \(n,m\)。意义如题所述。
接下来 \(m\) 行，每行两个坐标 \((x_1,y_1)\) 和 \((x_2,y_2)\)，代表一块地毯，左上角是 \((x_1,y_1)\)，右下角是 \((x_2,y_2)\)。
输出格式

输出 \(n\) 行，每行 \(n\) 个正整数。
第 \(i\) 行第 \(j\) 列的正整数表示 \((i,j)\) 这个格子被多少个地毯覆盖。
样例 #1

样例输入 #1

5 3
2 2 3 3
3 3 5 5
1 2 1 4

复制代码

样例输出 #1

0 1 1 1 0
0 1 1 0 0
0 1 2 1 1
0 0 1 1 1
0 0 1 1 1

复制代码

提示

样例解释

覆盖第一个地毯后：
\(0\)\(0\)\(0\)\(0\)\(0\)\(0\)\(1\)\(1\)\(0\)\(0\)\(0\)\(1\)\(1\)\(0\)\(0\)\(0\)\(0\)\(0\)\(0\)\(0\)\(0\)\(0\)\(0\)\(0\)\(0\)覆盖第一、二个地毯后：
\(0\)\(0\)\(0\)\(0\)\(0\)\(0\)\(1\)\(1\)\(0\)\(0\)\(0\)\(1\)\(2\)\(1\)\(1\)\(0\)\(0\)\(1\)\(1\)\(1\)\(0\)\(0\)\(1\)\(1\)\(1\)覆盖全部地毯后：
\(0\)\(1\)\(1\)\(1\)\(0\)\(0\)\(1\)\(1\)\(0\)\(0\)\(0\)\(1\)\(2\)\(1\)\(1\)\(0\)\(0\)\(1\)\(1\)\(1\)\(0\)\(0\)\(1\)\(1\)\(1\)数据范围

对于 \(20\%\) 的数据，有 \(n\le 50\)，\(m\le 100\)。
对于 \(100\%\) 的数据，有 \(n,m\le 1000\)。
题解

康康数据范围，\(n>n>>m; for(int i=1;i>a1>>b1>>a2>>b2; qz[a1][b1]++,qz[a1][b2+1]--,qz[a2+1][b1]--,qz[a2+1][b2+1]++; } // for(int i=1;i

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)