题解 | #E#

题目

输入

输出

思路

对于水淹没城市，然后生成联通块。可以逆向思考为，水褪去，城市的联通块合并为一起，转为并查集的思路。

提前通过公路，建立城市之间的连接。

对于不同高度的城市，可以放入数组，从大到小排序。

建立每个城市父亲节点指向自身，同时记录城市的大小。

时间倒流，对城市数组遍历，如果高度大于水高，则城市复活，然后找此城市的相邻城市，将其合并，记录空投数量。

特殊的，如果发放空投的连通城市集群大小为1，则每个城市都要空投。

完整代码

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAXN = 500005;
int n,m,x,d;
int h[MAXN];
int fa[MAXN];int sz [MAXN];
bool alive[MAXN];

 vector<int> e[MAXN];
long long good=0;

int find(int x){
    return fa[x]== x ? x : fa[x] = find(fa[x]);
}

void unite(int a,int b){
    a=find(a);
    b=find(b);
    if(a==b) return ;
    if(sz[a]<sz[b]) swap(a,b);
    if(sz[a]>=d) good--;
    if(sz[b]>=d) good--;
    
    fa[b]=a;
    sz[a]+=sz[b];
    if(sz[a]>=d) good++;
}


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m>>x>>d;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    vector<pair<int,int>> city;
    for(int i=1;i<=n;i++){
        city.push_back({h[i],i});
    }
    sort(city.begin(),city.end(),greater<>());
    
    vector<int> H(x);
    for(int i=0;i<x;i++){
        cin>>H[i];
    }
    
    vector<long long> ans(x);
    for(int i=1;i<=n;i++){
        fa[i]=i;
        sz[i]=1;
    }
    int it=0;
    for(int day=x-1;day>=0;day--){
        
        while(it<n&&city[it].first>H[day]){
            int u=city[it].second;
            alive[u]=true;
            
            if (d == 1) good++;
            
            for(auto v:e[u]){
                if(alive[v]) unite(u,v);
            }
            it++;
        }
        ans[day]=good;
    }
    for (auto v : ans) cout << v << "\n";
    return 0;
}