#P18467. LIS on Grid

LIS on Grid

LIS on Grid

给定一个有 nn 行、mm 列的网格。行从上到下编号为 1,2,…,n1,2,\ldots,n,列从左到右编号为 1,2,…,m1,2,\ldots,m,第 ii 行、第 jj 列的格子记为 (i,j)(i,j)。

你要将其中一些格子涂黑:对于每一列 jj,必须恰好涂黑 aja_j 个格子。

涂色后,你的代价是黑格的最长严格递增子序列长度。准确地说,它是满足下列条件的最大整数 kk:存在格子序列 (r1,c1),(r2,c2),…,(rk,ck)(r_1,c_1),(r_2,c_2),\ldots,(r_k,c_k),使得

  • 1≤r1<r2<⋯<rk≤n1\le r_1<r_2<\cdots<r_k\le n;
  • 1≤c1<c2<⋯<ck≤m1\le c_1<c_2<\cdots<c_k\le m;
  • 每个 (ri,ci)(r_i,c_i) 都是黑格。

求你能取得的最小代价,并输出一种达到该代价的涂色方案。

输入格式

第一行包含整数 tt(1≤t≤1051\le t\le10^5),表示测试用例数。随后依次描述每个测试用例。

每个测试用例第一行包含两个整数 n,mn,m(1≤n,m≤2⋅1051\le n,m\le2\cdot10^5,nm≤2⋅105nm\le2\cdot10^5),分别表示行数和列数。

第二行包含 mm 个整数 a1,a2,…,ama_1,a_2,\ldots,a_m(1≤aj≤n1\le a_j\le n),其中 aja_j 是第 jj 列必须涂黑的格子数。

保证所有测试用例的 nmnm 之和不超过 2⋅1052\cdot10^5。

输出格式

对于每个测试用例,首先输出一行一个整数,表示能够达到的最小代价。

随后输出 nn 行,每行是长度为 mm、仅由 . 和 # 组成的字符串。第 ii 行字符串的第 jj 个字符为 # 表示格子 (i,j)(i,j) 涂黑,为 . 表示该格子保持白色。

每列的黑格数必须恰为给定的 aja_j。可以输出任意一种最优方案,判题器按实际涂色检查。

原样例输入

4
2 4
1 1 1 1
3 3
3 3 3
4 4
4 3 2 1
4 5
2 3 4 3 2

原样例输出

1
....
####
3
###
###
###
2
###.
#...
####
##..
2
..###
.####
####.
###..

帮助理解

同一行的两个黑格不能同时出现在上述严格递增子序列中,同一列也不能。第一个样例将所有黑格放在同一行,代价为 11。第二个样例所有格子都必须为黑色,代价为 33。上面的输出完整保留原题提供的四个用例及其方案;其他最优方案同样合法。