题目大意

给定 $n$ 个城市和 $m$ 条道路，第 $i$ 条道路连接 $a_i$ 和 $b_i$，建造成本为 $2^i$。每个城市有奇偶性要求 $p_i$（$0$ 表示要求度数为偶数，$1$ 表示要求度数为奇数）。需要支持：

1. 输出初始时第 $k$ 便宜的满足条件的道路集合
2. 修改城市的奇偶性要求
3. 修改 $k$ 值
4. 查询当前方案是否包含某条道路

问题分析

度数约束与线性代数

这是一个典型的度数约束子图选择问题。对于无向图 $G=(V,E)$，每个顶点 $v$ 有度数奇偶性要求 $p_v$，我们需要选择边集 $S \subseteq E$ 使得对于每个顶点 $v$，$\deg_S(v) \equiv p_v \pmod{2}$。

在模 $2$ 的线性代数框架下，这个问题可以表述为：

设 $A$ 是图的关联矩阵（$|V| \times |E|$，在 $\mathbb{F}_2$ 上），$p$ 是需求向量，我们需要解方程：

其中 $x \in \{0,1\}^{|E|}$ 表示每条边是否被选择。

解空间结构

根据线性代数理论：

• 如果方程有解，解空间的维数为 $|E| - \text{rank}(A)$
• 解的数量为 $2^{|E| - \text{rank}(A)}$（如果存在）

对于连通图，关联矩阵的秩为 $|V|-1$（在 $\mathbb{F}_2$ 上），因此解空间维数为 $|E| - |V| + 1$。

成本优化与第 $k$ 小解

由于成本是 $2^i$ 且严格递增，这实际上构成了一个二进制表示。第 $i$ 条边是否选择对应二进制第 $i$ 位。

寻找第 $k$ 便宜的解等价于在解空间中按二进制表示（从低位到高位）寻找第 $k$ 小的向量。

算法思路

基础解法

1. 构建线性基：在 $\mathbb{F}_2$ 上求解 $Ax \equiv p$，找到一组基础解
2. 解空间表示：任何解可以表示为特解 + 齐次解空间的线性组合
3. 第 $k$ 小解：将自由变量按成本升序排列，$k$ 的二进制表示直接决定哪些自由变量被选择

高效实现

由于 $n, m \leq 5\times 10^5$，需要高效算法：

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

typedef long long ll;
const int MAXN = 500005;

// 并查集维护连通性
struct DSU {
    vector<int> parent, rank;
    DSU(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    
    bool unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        if (rank[x] == rank[y]) rank[x]++;
        return true;
    }
};

// 线性基模2
struct LinearBasis {
    vector<bitset<MAXN>> basis;
    vector<int> pivot;
    int rank;
    
    LinearBasis(int n) : basis(n), pivot(n, -1), rank(0) {}
    
    bool insert(bitset<MAXN> vec, int idx) {
        for (int i = 0; i < basis.size(); i++) {
            if (vec[i]) {
                if (pivot[i] == -1) {
                    basis[i] = vec;
                    pivot[i] = idx;
                    rank++;
                    return true;
                }
                vec ^= basis[i];
            }
        }
        return false;
    }
    
    bitset<MAXN> solve(bitset<MAXN> target) {
        bitset<MAXN> result;
        for (int i = 0; i < basis.size(); i++) {
            if (target[i]) {
                if (pivot[i] == -1) return bitset<MAXN>(); // 无解
                target ^= basis[i];
                result.set(pivot[i]);
            }
        }
        return result;
    }
};

class ParityRoads {
private:
    int n, m;
    vector<pair<int, int>> edges;
    vector<int> parity;
    ll k;
    vector<int> current_solution;
    
public:
    void init(int n, int m, vector<pair<int, int>> edges, vector<int> parity, ll k) {
        this->n = n;
        this->m = m;
        this->edges = edges;
        this->parity = parity;
        this->k = k;
        compute_solution();
    }
    
    void change_parity(int city) {
        parity[city] ^= 1;
        compute_solution();
    }
    
    void change_k(ll new_k) {
        k = new_k;
        compute_solution();
    }
    
    int query_edge(int edge_id) {
        if (current_solution.empty()) return -1;
        return current_solution[edge_id - 1];
    }
    
private:
    void compute_solution() {
        // 构建关联矩阵
        vector<bitset<MAXN>> equations(n);
        for (int i = 0; i < m; i++) {
            int u = edges[i].first - 1, v = edges[i].second - 1;
            equations[u].set(i);
            equations[v].set(i);
        }
        
        // 构建需求向量
        bitset<MAXN> target;
        for (int i = 0; i < n; i++) {
            if (parity[i]) target.set(i);
        }
        
        // 高斯消元求解
        LinearBasis basis(n);
        vector<int> free_vars;
        
        for (int i = 0; i < m; i++) {
            bitset<MAXN> eq;
            for (int j = 0; j < n; j++) {
                if (equations[j][i]) eq.set(j);
            }
            
            if (!basis.insert(eq, i)) {
                free_vars.push_back(i);
            }
        }
        
        // 检查解是否存在
        bitset<MAXN> particular = basis.solve(target);
        if (particular.none() && target.any()) {
            current_solution.clear();
            return;
        }
        
        // 构建第k小解
        current_solution.assign(m, 0);
        
        // 设置特解部分
        for (int i = 0; i < m; i++) {
            if (particular[i]) {
                current_solution[i] = 1;
            }
        }
        
        // 自由变量按k的二进制位设置
        sort(free_vars.begin(), free_vars.end());
        ll temp_k = k - 1; // k=1对应所有自由变量为0
        
        for (int i = 0; i < free_vars.size(); i++) {
            if (temp_k & (1LL << i)) {
                current_solution[free_vars[i]] ^= 1;
            }
        }
    }
};

关键优化

1. 稀疏矩阵处理：使用 bitset 高效处理稀疏的关联矩阵
2. 动态维护：当奇偶性要求改变时，只需重新计算特解，自由变量基不变
3. 第 $k$ 小计算：自由变量按边编号排序，$k$ 的二进制位直接映射

复杂度分析

• 预处理：$O(n^3/w)$，其中 $w$ 是字长（约64）
• 每次修改：$O(n^2/w)$ 重新计算特解
• 查询：$O(1)$

对于 $n, m \leq 5\times 10^5$，使用 bitset 优化后实际可运行。

总结

本题的核心是将度数约束问题转化为 $\mathbb{F}_2$ 上的线性方程组求解，利用线性基技术找到解空间，再根据成本的二进制特性高效找到第 $k$ 小解。

算法标签：图论、线性代数、高斯消元、bitset优化、解空间枚举