「NnOI R1-T2」风屿

Luogu

IDLGP9413

Time1000ms

Memory128MB

DifficultyP3

数学O2优化

风屿是一块 $ n $ 行，$ m $ 列的群岛，第 $ i $ 行第 $ j $ 列记为 $ (i,j) $。风屿的重力系统很奇怪，$ (i,j) $ 的重力系数 $ g_{i,j}=a_i+b_j $。$ a,b $ 是两个已知的长度分别为 $ n,m $ 的数组。我们定义岛 $ (x,y) $ 和 $ (z,w) $ **相邻**当且仅当 $ |x-z|+|y-w|=1 $，定义 $ (x,y) $ 和 $ (z,w) $ **连通**当且仅当两种情况至少有一种满足： * $ (x,y),(z,w) $ 相邻，且 $ g_{x,y}=g_{z,w} $。 * 存在另一个岛 $ (u,v) $ 使得 $ (x,y) $ 和 $ (u,v) $ 连通且 $ (u,v) $ 和 $ (z,w) $ 连通，也就是说，连通关系**具有传递性**。我们定义无序互异的岛集 $ \{(x_i,y_i)\} $ 为**同色连通块**，当且仅当岛集中任意两岛连通。找到最大的同色连通块，并求出大小和这样的块的个数。 ## Input **本题多测**，第一行一个正整数 $ T $，代表该测试点内测试数据组数。对于每组测试数据：第一行 $ n $，$ m $，表示风屿的行数和列数。接下来一行 $ n $ 个整数，代表 $ a $ 数组。接下来一行 $ m $ 个整数，代表 $ b $ 数组。 ## Output $ T $ 行，每行代表该组测试数据的答案（最大块大小和个数）。 [samples] ## Background 「与风为名，屿之齐鸣。」——风屿 ## Note ### 样例解释对于样例 $ 1 $：对于第 $ 1 $ 组测试数据，重力系数依次如下： ``` 2 3 4 5 3 4 5 6 3 4 5 6 ``` ``` 2 3 4 5 * # ? . * # ? . ``` 标记符号的为最大的同色连通块，大小为 $ 2 $，共 $ 4 $ 个。 ### 数据范围对于 $ 20\% $ 的数据，$ n,m \le 10^3 $。对于另 $ 20\% $ 的数据，所有 $ b_i $ 相等。对于另 $ 20\% $ 的数据，第二问答案一定为 $ 1 $。对于另 $ 20\% $ 的数据，$ T=1 $，这四档部分分表示的测试点集合互不包含。对于 $ 100\% $ 的数据，$ 1 \le T \le 5 $，$ 1 \le n,m \le 10^5 $，$ 1 \le a_i,b_i \le 10^9 $。 ### 题目来源 | 项目 | 人员 | |:-:|:-:| | idea | Kevin0501 | | std | Kevin0501 | data | EstasTonne | | check | EstasTonne | | solution | Kevin0501 |

Samples

Input #1

3
3 4
1 2 2
1 2 3 4
4 5
1 2 2 3
2 3 3 3 4
6 7
1 1 2 2 3 4
1 2 2 2 3 3 3

Output #1

2 4
6 1
6 4

API Response (JSON)

{
  "problem": {
    "name": "「NnOI R1-T2」风屿",
    "description": {
      "content": "风屿是一块 $ n $ 行，$ m $ 列的群岛，第 $ i $ 行第 $  j $ 列记为 $ (i,j) $。 风屿的重力系统很奇怪，$ (i,j) $ 的重力系数 $ g_{i,j}=a_i+b_j $。$ a,b $ 是两个已知的长度分别为 $ n,m $ 的数组。 我们定义岛 $ (x,y) $ 和 $ (z,w) $ **相邻**当且仅当 $ |x-z|+|y-w|=1 $，定义 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9413"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "风屿是一块 $ n $ 行，$ m $ 列的群岛，第 $ i $ 行第 $  j $ 列记为 $ (i,j) $。\n\n风屿的重力系统很奇怪，$ (i,j) $ 的重力系数 $ g_{i,j}=a_i+b_j $。$ a,b $ 是两个已知的长度分别为 $ n,m $ 的数组。\n\n我们定义岛 $ (x,y) $ 和 $ (z,w) $ **相邻**当且仅当 $ |x-z|+|y-w|=1 $，定义 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments