网易互娱第四题并查集+堆

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int hei;
    int pos;
    node(int p, int h) : pos(p), hei(h)
    {
    }

};

struct greaterr
{
    bool operator()(node &n1, node &n2)
    {
        if (n1.hei != n2.hei)
        {
            return n1.hei < n2.hei;
        }
        else
        {
            return n1.pos < n2.pos;
        }
    }
};

class UnionFind
{

private:
    vector<int> rank;
    vector<int> parent; 
    int count;          // 数据个数
    int ucount;         // 集合个数
    vector<int> isIn;

public:
    // 构造函数
    UnionFind(int count)
    {
        parent = vector<int>(count);
        rank = vector<int>(count);
        this->count = count;
        ucount = 0;
        for (int i = 0; i < count; i++)
        {
            parent[i] = i;
            rank[i] = 1;
            isIn.push_back(false);
        }
    }

    // 析构函数
    ~UnionFind()
    {
    }

    void join(int p)
    {
        if (!isIn[p])
        {
            ucount++;
            isIn[p] = true;
        }
    }


    int find(int p)
    {

        while (p != parent[p])
        {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }
        return p;
    }

    bool isConnected(int p, int q)
    {
        return find(p) == find(q);
    }

    void unionElements(int p, int q)
    {

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot)
            return;
        ucount--;

        if (rank[pRoot] < rank[qRoot])
        {
            parent[pRoot] = qRoot;
        }
        else if (rank[qRoot] < rank[pRoot])
        {
            parent[qRoot] = pRoot;
        }
        else
        {
            parent[pRoot] = qRoot;
            rank[qRoot] += 1;
        }
    }
    int getUCount()
    {
        return ucount;
    }
};

int main()
{
    int n;
    cin >> n;
    vector<int> h;
    priority_queue<node, vector<node>, greaterr> pq;
    vector<bool> isDown;
    for (int i = 0; i < n; i++)
    {
        int temp;
        cin >> temp;
        h.push_back(temp);
        pq.push(node(i, h[i]));
        isDown.push_back(true);
    }

    int q;
    cin >> q;
    vector<int> w;
    map<int, int> m;
    for (int i = 0; i < q; i++)
    {
        int temp;
        cin >> temp;
        w.push_back(temp);
        m[temp] = 1;
    }
    UnionFind uf(n);

    for (auto it = m.rbegin(); it != m.rend(); it++)
    {
        node he = pq.top(); // highest node
        while (he.hei > it->first && !pq.empty())
        {
            uf.join(he.pos);
            isDown[he.pos] = false;
            if (he.pos != 0 && !isDown[he.pos - 1])
            {
                uf.unionElements(he.pos, he.pos - 1);
            }
            if (he.pos != h.size() - 1 && !isDown[he.pos + 1])
            {
                uf.unionElements(he.pos, he.pos + 1);
            }
            pq.pop();
            he = pq.top();
        }
        it->second = uf.getUCount();
    }
    for (auto e : w)
    {
        cout << m[e] << endl;
    }
    return 0;
}