[POI 2020/2021 R1] Tablica binarna / 01 矩阵

Luogu
IDLGP9298
Time1000ms
Memory128MB
DifficultyP2
2020POI(波兰)
矩阵 $A$ 有 $n$ 行 $m$ 列,行自上到下编号为 $1$ 至 $n$,列自左到右编号为 $1$ 到 $m$,因此可以用 $(i,j)$ 表示矩阵的第 $i$ 行第 $j$ 列的元素。且矩阵 $A$ 中每个元素的值为 $0$ 或 $1$。 最初,矩阵内的所有元素的值均为 $0$。接下来可以对该矩阵执行 $q$ 次修改操作。每次操作将给出四个参数 $i_1,j_1,i_2,j_2$,表示将以 $(i_1,j_1)$ 为左上角,$(i_2,j_2)$ 为右下角的矩形内的所有元素的值翻转(从 $0$ 变成 $1$,或从 $1$ 变为 $0$)。 如果一次操作中,矩形的左上角与矩阵的左上角重合(即 $i_1=j_1=1$),则称这次修改操作是**简单的**。 现在你想要知道,在每次对矩阵执行修改操作后,需要执行至少多少次**简单的**修改操作,使得矩阵内所有元素的值全部变为 $0$。 ## Input 输入第一行三个整数 $n,m,q$,分别代表矩阵的行数,列数,操作的次数。 接下来 $q$ 行,每行四个整数 $i_1,j_1,i_2,j_2$,描述一次修改操作。保证 $1 \leq i_1 \leq i_2 \leq n$,$1 \leq j_1 \leq j_2 \leq m$。 ## Output 输出 $q$ 行。第 $i$ 行输出一个整数,表示在第 $i$ 次修改过后,需要执行至少多少次**简单的**修改操作,使得矩阵内所有元素的值全部变为 $0$。 [samples] ## Background **题目译自 [XXVIII Olimpiada Informatyczna – I etap](https://sio2.mimuw.edu.pl/c/oi28-1/dashboard/) [Tablica binarna](https://sio2.mimuw.edu.pl/c/oi28-1/p/tab/)。** ## Note 【样例解释1】: ![](https://s1.ax1x.com/2023/04/04/pp4jI2T.png) 【数据范围】: 所有测试点均满足:$1 \leq n,m \leq 10^3$,$1 \leq q \leq 10^5$。 | 子任务编号 | 约束 | 分值 | | :----------: | :-------------: | :----: | | $1$ | $n,m \leq 2$ | $14$ | | $2$ | $q=1$ | $16$ | | $3$ | $n=1$ | $21$ | | $4$ | $n,m \leq 10$ | $9$ | | $5$ | $n,m \leq 80$ | $10$ | | $6$ | 无附加约束 | $30$ |
Samples
Input #1
2 3 3
1 2 2 2
1 1 2 1
1 2 1 3
Output #1
2
1
3
Input #2
4 4 16
1 1 1 1
1 2 1 2
1 3 1 3
1 4 1 4
2 1 2 1
2 2 2 2
2 3 2 3
2 4 2 4
3 1 3 1
3 2 3 2
3 3 3 3
3 4 3 4
4 1 4 1
4 2 4 2
4 3 4 3
4 4 4 4
Output #2
1
1
1
1
3
3
3
1
3
3
3
1
3
3
3
1
API Response (JSON)
{
  "problem": {
    "name": "[POI 2020/2021 R1] Tablica binarna / 01 矩阵",
    "description": {
      "content": "矩阵 $A$ 有 $n$ 行 $m$ 列,行自上到下编号为 $1$ 至 $n$,列自左到右编号为 $1$ 到 $m$,因此可以用 $(i,j)$ 表示矩阵的第 $i$ 行第 $j$ 列的元素。且矩阵 $A$ 中每个元素的值为 $0$ 或 $1$。 最初,矩阵内的所有元素的值均为 $0$。接下来可以对该矩阵执行 $q$ 次修改操作。每次操作将给出四个参数 $i_1,j_1,i_2,j_2$,表示将",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9298"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "矩阵 $A$ 有 $n$ 行 $m$ 列,行自上到下编号为 $1$ 至 $n$,列自左到右编号为 $1$ 到 $m$,因此可以用 $(i,j)$ 表示矩阵的第 $i$ 行第 $j$ 列的元素。且矩阵 $A$ 中每个元素的值为 $0$ 或 $1$。\n\n最初,矩阵内的所有元素的值均为 $0$。接下来可以对该矩阵执行 $q$ 次修改操作。每次操作将给出四个参数 $i_1,j_1,i_2,j_2$,表示将...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments