题目描述
有一个 n 行 m 列的网格,每个格子有一个颜色。每次询问给出一个区间 [l,r],只保留该区间内的列,求剩下的网格中有多少个四连通颜色块。只有上下或左右相邻且颜色相同的格子才能直接连通。
输入格式
第一行三个正整数 n,m,q,表示网格行数、列数和询问次数。
接下来 n 行,每行 m 个正整数 ci,j,表示每个格子的颜色。
接下来 q 行,每行两个整数 l,r,表示保留的列区间,1≤l≤r≤m。
输出格式
每次询问输出一行一个正整数,表示颜色块的个数。
样例
4 5 4
1 1 1 1 1
1 2 2 3 3
1 1 1 2 5
4 4 5 5 5
1 5
2 5
1 2
4 5
6
7
3
4
原赛样例 2 见下发文件。
数据范围
- 对于 20% 的数据,n,m≤100,q≤1000。
- 对于 40% 的数据,n,m≤500,q≤1000。
- 对于 60% 的数据,n,m≤500,q≤20000。
- 对于 80% 的数据,n,m≤1000,q≤100000。
- 对于所有评测数据,10≤n,m≤1000,1≤q≤200000,1≤ci,j≤109。
原 PDF 题面