UVA1665 Islands （并查集）

补题，逆序考虑每个询问的时间，这样每次就变成出现新岛屿，然后用并查集合并统计。fa = -1表示没出现。

以前写过，但是几乎忘了，而且以前写得好丑的，虽然常数比较小，现在重新写练练手。每个单词后面都要加空格不然PE

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
const int maxq = 1e5+1;

int q[maxq];
int pa[maxn*maxn];

int Find(int x){ return x==pa[x]?x:pa[x]=Find(pa[x]); }

int h[maxn][maxn];

struct Node
{
    int x,y,val;
}nd[maxn*maxn];


bool operator < (const Node &x,const Node &y) { return  x.val < y.val; }

int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};

int main()
{
    //freopen("in.txt","r",stdin);
    int Z; scanf("%d",&Z);
    while(Z--){
        int m,n; scanf("%d%d",&m,&n);
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                scanf("%d",h[i]+j);
                int t = i*n+j;
                nd[t].x = i; nd[t].y = j;
                nd[t].val = h[i][j];
            }
        }

        sort(nd,nd+m*n);
        memset(pa,-1,sizeof(int)*(m*n));
        int Ts; scanf("%d",&Ts);
        for(int i = 0; i < Ts; i++){
            scanf("%d",q+i);
        }

        int k = m*n-1;
        int ans = 0;
        for(int i = Ts-1; i >= 0; i--){
            if(q[i]<nd[k].val){
                while(k>=0&&q[i]<nd[k].val){
                    int id = nd[k].x*n+nd[k].y;
                    if(!~pa[id]) ans++,pa[id] = id;
                    for(int d = 0; d < 4; d++){
                        int nx = nd[k].x+dx[d], ny = nd[k].y+dy[d];
                        if(nx>=0&&nx<m&&ny>=0&&ny<n&&h[nx][ny]>q[i]){
                            int nid = nx*n+ny;
                            if(~pa[nid]) {
                                int a = Find(nid), b = Find(id);
                                if(a != b) {
                                    pa[a] = b;
                                    ans--;
                                }
                            }
                        }
                    }
                    k--;
                }
                if(k<0){
                    for(;i>=0;i--){
                        q[i] = ans;
                    }
                    break;
                }
            }
            q[i] = ans;
        }
        for(int i = 0; i < Ts; i++) printf("%d ",q[i]);
        putchar('
');
    }
    return 0;
}