English · Original
Chinese · Translation
Formal · Original
In his spare time Vladik estimates beauty of the flags.
Every flag could be represented as the matrix _n_ × _m_ which consists of positive integers.
Let's define the beauty of the flag as number of components in its matrix. We call component a set of cells with same numbers and between any pair of cells from that set there exists a path through adjacent cells from same component. Here is the example of the partitioning some flag matrix into components:
<center></center>But this time he decided to change something in the process. Now he wants to estimate not the entire flag, but some segment. Segment of flag can be described as a submatrix of the flag matrix with opposite corners at (1, _l_) and (_n_, _r_), where conditions 1 ≤ _l_ ≤ _r_ ≤ _m_ are satisfied.
Help Vladik to calculate the beauty for some segments of the given flag.
## Input
First line contains three space-separated integers _n_, _m_, _q_ (1 ≤ _n_ ≤ 10, 1 ≤ _m_, _q_ ≤ 105) — dimensions of flag matrix and number of segments respectively.
Each of next _n_ lines contains _m_ space-separated integers — description of flag matrix. All elements of flag matrix is positive integers not exceeding 106.
Each of next _q_ lines contains two space-separated integers _l_, _r_ (1 ≤ _l_ ≤ _r_ ≤ _m_) — borders of segment which beauty Vladik wants to know.
## Output
For each segment print the result on the corresponding line.
[samples]
## Note
Partitioning on components for every segment from first test case:
在空闲时间，Vladik 会评估旗帜的美丽度。
每面旗帜可以用一个 #cf_span[n × m] 的矩阵表示，其中包含正整数。
我们定义旗帜的美丽度为其矩阵中连通分量的数量。连通分量是指由相同数字的单元格组成的集合，且该集合中任意两个单元格之间都存在一条通过相邻同值单元格构成的路径。下图展示了一个将旗帜矩阵划分为连通分量的例子：
但这一次，他决定在过程中做一些改变。现在他想评估的不是整个旗帜，而是一些子段。旗帜的子段可以描述为一个子矩阵，其左上角为 #cf_span[(1, l)]，右下角为 #cf_span[(n, r)]，满足条件 #cf_span[1 ≤ l ≤ r ≤ m]。
请帮助 Vladik 计算给定旗帜某些子段的美丽度。
第一行包含三个用空格分隔的整数 #cf_span[n], #cf_span[m], #cf_span[q]（#cf_span[1 ≤ n ≤ 10], #cf_span[1 ≤ m, q ≤ 10^5]）——分别表示旗帜矩阵的行数、列数和查询的子段数量。
接下来的 #cf_span[n] 行，每行包含 #cf_span[m] 个用空格分隔的整数——表示旗帜矩阵的描述。矩阵中所有元素均为不超过 #cf_span[10^6] 的正整数。
接下来的 #cf_span[q] 行，每行包含两个用空格分隔的整数 #cf_span[l], #cf_span[r]（#cf_span[1 ≤ l ≤ r ≤ m]）——表示 Vladik 想要知道美丽度的子段边界。
对于每个子段，请在对应行输出结果。
第一个测试用例中每个子段的连通分量划分如下：
## Input
第一行包含三个用空格分隔的整数 #cf_span[n], #cf_span[m], #cf_span[q]（#cf_span[1 ≤ n ≤ 10], #cf_span[1 ≤ m, q ≤ 10^5]）——分别表示旗帜矩阵的行数、列数和查询的子段数量。接下来的 #cf_span[n] 行，每行包含 #cf_span[m] 个用空格分隔的整数——表示旗帜矩阵的描述。矩阵中所有元素均为不超过 #cf_span[10^6] 的正整数。接下来的 #cf_span[q] 行，每行包含两个用空格分隔的整数 #cf_span[l], #cf_span[r]（#cf_span[1 ≤ l ≤ r ≤ m]）——表示 Vladik 想要知道美丽度的子段边界。
## Output
对于每个子段，请在对应行输出结果。
[samples]
## Note
第一个测试用例中每个子段的连通分量划分如下：
**Definitions:**
- Let $ A \in \mathbb{Z}^{n \times m} $ be a matrix of positive integers, with $ 1 \leq n \leq 10 $, $ 1 \leq m, q \leq 10^5 $.
- A **component** is a maximal connected set of cells (under 4-directional adjacency: up, down, left, right) such that all cells in the set have the same value.
- For a segment $ [l, r] $ with $ 1 \leq l \leq r \leq m $, define the **submatrix** $ A_{[l:r]} \in \mathbb{Z}^{n \times (r-l+1)} $ as the submatrix consisting of columns $ l $ through $ r $.
**Given:**
- Matrix $ A $ of size $ n \times m $.
- $ q $ queries, each specifying a segment $ [l, r] $.
**Objective:**
For each query $ [l, r] $, compute the number of connected components in the submatrix $ A_{[l:r]} $, where connectivity is defined via 4-directional adjacency and cells must have equal values to be in the same component.
**Formal Output:**
For each query $ (l, r) $, output $ C(A_{[l:r]}) $, where $ C(B) $ denotes the number of connected components in matrix $ B $ under the above definition.
API Response (JSON)
{
"problem": {
"name": "E. Vladik and Entertaining Flags",
"description": {
"content": "In his spare time Vladik estimates beauty of the flags. Every flag could be represented as the matrix _n_ × _m_ which consists of positive integers. Let's define the beauty of the flag as number of ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF811E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "In his spare time Vladik estimates beauty of the flags.\n\nEvery flag could be represented as the matrix _n_ × _m_ which consists of positive integers.\n\nLet's define the beauty of the flag as number of ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "在空闲时间，Vladik 会评估旗帜的美丽度。\n\n每面旗帜可以用一个 #cf_span[n × m] 的矩阵表示，其中包含正整数。\n\n我们定义旗帜的美丽度为其矩阵中连通分量的数量。连通分量是指由相同数字的单元格组成的集合，且该集合中任意两个单元格之间都存在一条通过相邻同值单元格构成的路径。下图展示了一个将旗帜矩阵划分为连通分量的例子：\n\n但这一次，他决定在过程中做一些改变。现在他想评估的不是整个旗...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n\n- Let $ A \\in \\mathbb{Z}^{n \\times m} $ be a matrix of positive integers, with $ 1 \\leq n \\leq 10 $, $ 1 \\leq m, q \\leq 10^5 $.\n- A **component** is a maximal connected set of cells ...",
"is_translate": false,
"language": "Formal"
}
]
}