#P12089. [2024年联测]旗帜

    ID: 11238 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600省选/NOI-普通并查集路径压缩按大小合并增量维护无向连通分量边界连通关系关键边压缩

[2024年联测]旗帜

题目描述

有一个 nn 行 mm 列的网格,每个格子有一个颜色。每次询问给出一个区间 [l,r][l,r],只保留该区间内的列,求剩下的网格中有多少个四连通颜色块。只有上下或左右相邻且颜色相同的格子才能直接连通。

输入格式

第一行三个正整数 n,m,qn,m,q,表示网格行数、列数和询问次数。

接下来 nn 行,每行 mm 个正整数 ci,jc_{i,j},表示每个格子的颜色。

接下来 qq 行,每行两个整数 l,rl,r,表示保留的列区间,1≤l≤r≤m1\le l\le r\le 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%20\% 的数据,n,m≤100n,m\le100,q≤1000q\le1000。
  • 对于 40%40\% 的数据,n,m≤500n,m\le500,q≤1000q\le1000。
  • 对于 60%60\% 的数据,n,m≤500n,m\le500,q≤20000q\le20000。
  • 对于 80%80\% 的数据,n,m≤1000n,m\le1000,q≤100000q\le100000。
  • 对于所有评测数据,10≤n,m≤100010\le n,m\le1000,1≤q≤2000001\le q\le200000,1≤ci,j≤1091\le c_{i,j}\le10^9。

原 PDF 题面