CF1814F Communication Towers 题解

题目分析

每个通信塔初始状态为开（1）或关（0），目标是所有塔状态为关（0）。每次操作可选择单个塔翻转（状态取反）或区间翻转（区间内所有塔状态取反），求最少操作次数。

算法思路

1. 问题转化：塔的状态由初始状态和翻转次数的奇偶性决定。初始为开（1）的塔需翻转奇数次，初始为关（0）的塔需翻转偶数次（含0次）。
2. 线段树分治：将区间翻转操作分解为线段树的节点操作，通过分治处理不同区间的依赖关系。
3. 并查集维护：用并查集（DSU）维护塔的翻转状态等价关系，合并无冲突的操作，减少重复计算。

解题步骤

1. 构建线段树：将区间操作分解为线段树节点，每个节点存储区间范围及是否需要翻转。
2. 分治处理：递归处理线段树节点，对单点区间直接判断是否需翻转，对区间节点标记翻转并传递至子节点。
3. 并查集合并：当子节点存在冲突时，用并查集合并等价状态，记录必要操作次数。

代码实现

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

const int MAXN = 1e5 + 5;

int n, a[MAXN];
int ans = 0;

struct DSU {
    vector<int> parent, rank;
    DSU(int size) : parent(size + 1), rank(size + 1, 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;
        if (rank[u] < rank[v]) swap(u, v);
        parent[v] = u;
        rank[u] += rank[v];
        return true;
    }
};

struct Node {
    int l, r;
    bool flip;
    Node *left, *right;
    Node(int l, int r) : l(l), r(r), flip(false), left(nullptr), right(nullptr) {}
};

Node* build(int l, int r) {
    Node* node = new Node(l, r);
    if (l == r) return node;
    int mid = (l + r) / 2;
    node->left = build(l, mid);
    node->right = build(mid + 1, r);
    return node;
}

void solve(Node* node, int L, int R, DSU& dsu) {
    if (node->l > R || node->r < L) return;
    if (L <= node->l && node->r <= R) {
        if (node->l == node->r) {
            int u = node->l;
            int root = dsu.find(u);
            if (a[u] == 1) {
                ans++;
                dsu.unite(u, u + n);
            }
            return;
        }
        node->flip ^= true;
        return;
    }
    solve(node->left, L, R, dsu);
    solve(node->right, L, R, dsu);
    if (node->left->flip && node->right->flip) {
        node->flip ^= true;
        node->left->flip = node->right->flip = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    Node* root = build(1, n);
    DSU dsu(2 * n);
    solve(root, 1, n, dsu);
    cout << ans << endl;
    return 0;
}

C132 线段树分治+并查集 CF1814F Communication Towers