题解 P3397 【地毯】

· · 题解

n*n的矩阵，每次给一个子矩阵 区间+1 。最后输出整个矩阵。

优化。用二维线段树或二维树状数组完成上面的操作。

复杂度单次O(log^2n) ，总复杂度 O(mlog^2n+n^2)，足以吊打此题。

但是NOIP是不会考二维数据结构的

考虑这个问题的一维版：一个序列，最开始全是 0 .每次区间加 1 ,最后输出每个数。

于是有一种叫做“差分”的奇技淫巧：

假设我们现在要给[2,5]这个区间加一。原来的序列是：

0 0 0 0 0 0 0 0

这时候我们在2上面打 +1 标记， 6 上面打 -1 标记。那么现在的序列是：

0 +1 0 0 0 -1 0

有什么用呢？从左往右扫描这个数组，记录当前经过的标签之和。这个和就是对应那个数的答案。

这样，对于每个区间加操作，只需要O(1) 的时间打上标记。

最后扫描输出即可。

现在把问题拓展到二维。假设我们要覆盖[(2,2),(5,5)] ，那么标记便可以这样打：

0 0 0 0 0 0
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 +1 0 0 0 -1
0 0 0 0 0 0

即在每一行都按照一维的方式来操作

int sum=0,i,j;
   for(i=1;i<=n+1;i++)
      for(j=1;j<=n+1;j++)
         sum+=flag[i][j],real[i][j]=sum;

之后 real 数组里就存了最后的矩阵。输出即可。

这个算法的复杂度是每次打标记O(n) ，总复杂度是O(mn+n^2)