#P14735. [Bulgarian2017春季赛]rectcnt

    ID: 13951 传统题 3000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400数据结构单调栈数学前缀和线段树

[Bulgarian2017春季赛]rectcnt

题目描述

给定一个 N×NN \times N 的 01 矩阵。你的任务是编写程序 rectcnt,完成以下工作:

  1. 计算所有边平行于矩阵边界、且内部只包含 0 的子矩形数量;
  2. 处理若干次修改操作,每次把某个位置 (i,j)(i,j) 的值翻转:0 变 1,1 变 0;
  3. 在初始状态以及每次修改之后,都重新输出只包含 0 的子矩形总数。

输入格式

第一行输入两个正整数 N,QN,Q,分别表示矩阵大小和操作次数。

接下来 NN 行,每行一个长度为 NN 的仅由 0 和 1 组成的字符串,表示矩阵初始状态。

接下来 QQ 行,每行两个整数 i,ji,j,表示把第 ii 行、第 jj 列的元素翻转。矩阵下标从 0 开始。

输出格式

输出 Q+1Q+1 行:

  • 第 1 行输出初始矩阵中只包含 0 的子矩形数量;
  • 第 k+1k+1 行输出第 kk 次操作完成后的答案。

数据范围

  • 1≤N≤10001 \le N \le 1000
  • 1≤Q≤100001 \le Q \le 10000

样例

输入

4 3
0001
0100
1000
0010
1 2
1 1
2 0

输出

29
23
31
45

样例解释

初始时:

  • 有 1212 个 1×11\times1 矩形;
  • 66 个 1×21\times2 矩形;
  • 22 个 1×31\times3 矩形;
  • 66 个 2×12\times1 矩形;
  • 11 个 2×22\times2 矩形;
  • 22 个 3×13\times1 矩形。

总数为:

12+6+2+6+1+2=29.12+6+2+6+1+2=29.

第一次操作后:

  • 有 1111 个 1×11\times1 矩形;
  • 55 个 1×21\times2 矩形;
  • 22 个 1×31\times3 矩形;
  • 44 个 2×12\times1 矩形;
  • 11 个 3×13\times1 矩形。

总数为:

11+5+2+4+1=23.11+5+2+4+1=23.

第二次操作后:

  • 有 1212 个 1×11\times1 矩形;
  • 66 个 1×21\times2 矩形;
  • 22 个 1×31\times3 矩形;
  • 66 个 2×12\times1 矩形;
  • 11 个 2×22\times2 矩形;
  • 33 个 3×13\times1 矩形;
  • 11 个 4×14\times1 矩形。

总数为:

12+6+2+6+1+3+1=31.12+6+2+6+1+3+1=31.

第三次操作后:

  • 有 1313 个 1×11\times1 矩形;
  • 77 个 1×21\times2 矩形;
  • 33 个 1×31\times3 矩形;
  • 11 个 1×41\times4 矩形;
  • 88 个 2×12\times1 矩形;
  • 33 个 2×22\times2 矩形;
  • 55 个 3×13\times1 矩形;
  • 22 个 3×23\times2 矩形;
  • 22 个 4×14\times1 矩形;
  • 11 个 4×24\times2 矩形。

总数为:

13+7+3+1+8+3+5+2+2+1=45.13+7+3+1+8+3+5+2+2+1=45.

子任务

子任务 分值 NN 上限 QQ 上限
1 15 400 0
2 25 1000
3 20 1000 0
4 40 10000

对于某一子任务,只有当该子任务的所有测试点都正确时,才能获得该子任务的分数。