题目
给出一张 N*M 的图，图中每个点有一个权值，代表这个点的高度，这个图
因为下了雨，所以每秒钟海平面的高度会上升 1，所以在某些时间，一些点会被
完全的淹没掉，现在给出 Q 个询问，每个询问给出一个时间 t，表示查询在时间
t 时还没有被淹的点所组成的连通块个数.
输入描述：
第一行两个整数 N，M
接下来 N 行，每行 M 个整数，分别表示第(i,j)点的高度.
接下来一个整数 Q，表示询问个数
接下来一行 Q 个整数 t[i]，表示第 i 次询问时的时间
输出描述：
输出 Q 行，依次输出每个询问的答案.
样例输入：
4 5
1 2 3 3 1
1 3 2 2 1
2 1 3 4 3
1 2 2 2 2
5
1 2 3 4 5
样例输出：
2
3
1
0
0
数据范围：
60%的数据保证：1<=N,M<=1000,1<=Q<=10^5
保证 1<=高度<=10^5 , 0<=t <= 10^5
100%的数据保证：1<=N,M<=1000,1<=Q<=10^5
保证 1<=高度<=10^9 ,0<= t <= 10^9
时间排，高度排，上下左右突突突，没了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define R(a,b,c) for(register int a = (b); a <= (c); ++a)
#define nR(a,b,c) for(register int a = (b); a >= (c); --a)
#define Fill(a,b) memset(a, b, sizeof(a))
#define Swap(a,b) ((a) ^= (b) ^= (a) ^= (b))
#define ON_DEBUGG
#ifdef ON_DEBUGG
#define D_e_Line printf("-----------
")
#define D_e(x) std::cout << (#x) << " : " <<x << "
"
#define FileOpen() freopen("in.txt", "r", stdin)
#define FileSave() freopen("out.txt", "w", stdout)
#define Pause() system("pause")
#include <ctime>
#define TIME() fprintf(stderr, "
TIME : %.3lfms
", clock() * 1000.0 / CLOCKS_PER_SEC)
#else
#define D_e_Line ;
#define D_e(x) ;
#define FileOpen() ;
#define FilSave ;
#define Pause() ;
#define TIME() ;
#endif
struct ios {
template<typename ATP> ios& operator >> (ATP &x) {
x = 0; int f = 1; char c;
for(c = getchar(); c < '0' || c > '9'; c = getchar()) if(c == '-') f = -1;
while(c >= '0' && c <= '9') x = x * 10 + (c ^ '0'), c = getchar();
x *= f;
return *this;
}
}io;
using namespace std;
template<typename ATP> inline ATP Min(ATP a, ATP b) {
return a < b ? a : b;
}
template<typename ATP> inline ATP Max(ATP a, ATP b) {
return a > b ? a : b;
}
template<typename ATP> inline ATP Abs(ATP a) {
return a < 0 ? -a : a;
}
const int N = 1e3 + 7;
const int M = 1e5 + 7;
struct Ques {
int tim, id;
bool operator < (const Ques &com) const {
return tim > com.tim;
}
} q[M];
int ans[M];
struct P {
int h, x, y;
bool operator < (const P &com) const {
return h > com.h;
}
} a[N * N];
//#define id(i,j) (((i) - 1) * (m) + (j))
int n, m;
inline int id(int x, int y) {
return (x - 1) * m + y;
}
int fa[N * N], siz[N * N];
inline int Find(int x) {
return x == fa[x] ? x : fa[x] = Find(fa[x]);
}
int tot;
inline void Merge(int x, int y) {
x = Find(x), y = Find(y);
if(x == y) return;
if(siz[x] > siz[y]) Swap(x, y);
fa[x] = y;
siz[y] += siz[x];
--tot;
}
int vis[N][N];
int main() {
freopen("C.in", "r", stdin);
freopen("C.out", "w", stdout);
io >> n >> m;
R(i,1,n){
R(j,1,m){
int x;
io >> x;
a[id(i, j)] = (P){ x, i, j};
fa[id(i, j)] = id(i, j);
siz[id(i, j)] = 1;
}
}
int Q;
io >> Q;
R(i,1,Q){
io >> q[i].tim;
q[i].id = i;
}
sort(q + 1, q + Q + 1);
sort(a + 1, a + n * m + 1);
int st = 1;
while(q[st].tim > a[1].h) ++st;
int j = 1;
R(i,st,Q){
while(a[j].h > q[i].tim){
int x = a[j].x, y = a[j].y;
vis[x][y] = true;
++tot;
if(vis[x - 1][y]) Merge(id(x, y), id(x - 1, y));
if(vis[x + 1][y]) Merge(id(x, y), id(x + 1, y));
if(vis[x][y - 1]) Merge(id(x, y), id(x, y - 1));
if(vis[x][y + 1]) Merge(id(x, y), id(x, y + 1));
++j;
}
ans[q[i].id] = tot;
}
R(i,1,Q) printf("%d
", ans[i]);
return 0;
}
/*
4 5
1 2 3 3 1
1 3 2 2 1
2 1 3 4 3
1 2 2 2 2
5
1 2 3 4 5
*/
