题目传送门
题目思路
本质是差分，用O(1)的复杂度来表示覆盖，比如对于:
0 0 0 0 0 0 0
需要覆盖[2,5]，就设2为1，6为-1。这样输出的时候就是当前的前缀和：
0 1 0 0 0 -1 0
二维的可以对每一行都这么操作，复杂度为O(mn+n^2)，mn是m个输入，n的标记复杂度（因为需要对每一行都这么操作），n方复原输出
也可以尝试二维差分，设b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]，然后每次修改就直接++b[x1][y1],--b[x2+1][y1],--b[x1][y2+1],++b[x2+1][y2+1]即可。最后再直接a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j]还原出原序列即可
AC代码
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
vector<vector<int>> a(n + 1, vector<int>(n + 1, 0));
for (int i = 0; i < m; i++)
{
int x1, y1;
int x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int j = x1 - 1; j < x2; j++)
{
a[j][y1 - 1]++;
a[j][y2]--;
}
}
for (int i = 0; i < n; i++)
{
long long str = 0;
for (int j = 0; j < n - 1; j++)
{
str += a[i][j];
cout << str << " ";
}
str += a[i][n - 1];
cout << str << endl;
}
return 0;
}