CF1681F Unique Occurrences

视频讲解

C133 线段树分治+并查集 CF1681F Unique Occurrences

解题思路

本题采用线段树分治与并查集结合的方法。线段树分治用于处理区间内元素的出现问题，通过将区间分解为多个子区间，在每个子区间内进行处理；并查集用于维护元素之间的连接关系，确保每个元素的出现次数符合题目要求。

代码实现

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

struct DSU {
    vector<int> parent;
    DSU(int n) : parent(n + 1) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int u) {
        if (parent[u] != u) parent[u] = find(parent[u]);
        return parent[u];
    }
    bool unite(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        parent[v] = u;
        return true;
    }
};

struct Node {
    int l, r;
    vector<int> vals;
    Node *left, *right;
    Node(int l, int r) : l(l), r(r), left(nullptr), right(nullptr) {}
};

Node* build(int l, int r, vector<int>& a) {
    Node* node = new Node(l, r);
    if (l == r) {
        node->vals.push_back(a[l]);
        return node;
    }
    int mid = (l + r) / 2;
    node->left = build(l, mid, a);
    node->right = build(mid + 1, r, a);
    node->vals.reserve(node->left->vals.size() + node->right->vals.size());
    node->vals.insert(node->vals.end(), node->left->vals.begin(), node->left->vals.end());
    node->vals.insert(node->vals.end(), node->right->vals.begin(), node->right->vals.end());
    return node;
}

void solve(Node* node, DSU& dsu, vector<bool>& res) {
    if (!node) return;
    if (node->l == node->r) {
        int x = node->vals[0];
        if (dsu.find(x) != dsu.find(x + 100000)) {
            dsu.unite(x, x + 100000);
        }
        return;
    }
    solve(node->left, dsu, res);
    solve(node->right, dsu, res);
    for (int x : node->vals) {
        if (dsu.find(x) == dsu.find(x + 100000)) {
            res[node->l] = res[node->r] = true;
            return;
        }
    }
    for (int x : node->vals) {
        dsu.unite(x, x + 100000);
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    Node* root = build(0, n - 1, a);
    DSU dsu(200000);
    vector<bool> res(n, false);
    solve(root, dsu, res);
    for (bool b : res) {
        cout << (b ? "YES" : "NO") << " ";
    }
    return 0;
}

C133 线段树分治+并查集 CF1681F Unique Occurrences