結果

問題 No.3423 Minimum Xor Query
コンテスト
ユーザー Aoxiang Cui
提出日時 2026-01-23 14:07:47
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
WA  
実行時間 -
コード長 6,501 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,238 ms
コンパイル使用メモリ 185,436 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-23 14:07:53
合計ジャッジ時間 5,551 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 7 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <set>

using namespace std;

// 定义常量
const int INF = 1e9 + 7;
const int MAXN = 20005;

// 全局变量
int N, Q;
int A[MAXN]; // 原数组

// 排序后的结构: (数值, 原始下标)
vector<pair<int, int>> sorted_A;

// 每个原始下标位置可能对应多个相邻对的异或值（因为可能会有多个对的max_index相同）
// 使用 multiset 维护每个下标位置当前的所有候选异或值
multiset<int> idx_contributions[MAXN];

// 线段树：维护区间最小值
int tree[4 * MAXN];

// 更新线段树单点
void update_tree(int node, int start, int end, int idx, int val) {
    if (start == end) {
        tree[node] = val;
        return;
    }
    int mid = (start + end) / 2;
    if (idx <= mid) update_tree(2 * node, start, mid, idx, val);
    else update_tree(2 * node + 1, mid + 1, end, idx, val);
    tree[node] = min(tree[2 * node], tree[2 * node + 1]);
}

// 查询线段树区间最小值
int query_tree(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return INF;
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    return min(query_tree(2 * node, start, mid, l, r),
               query_tree(2 * node + 1, mid + 1, end, l, r));
}

// 辅助函数：向系统添加一对相邻元素的贡献
void add_contribution(const pair<int, int>& p1, const pair<int, int>& p2) {
    int xor_val = p1.first ^ p2.first;
    int max_idx = max(p1.second, p2.second);

    idx_contributions[max_idx].insert(xor_val);
    // 更新线段树为该位置当前的最小值
    update_tree(1, 1, N, max_idx, *idx_contributions[max_idx].begin());
}

// 辅助函数：从系统移除一对相邻元素的贡献
void remove_contribution(const pair<int, int>& p1, const pair<int, int>& p2) {
    int xor_val = p1.first ^ p2.first;
    int max_idx = max(p1.second, p2.second);

    auto it = idx_contributions[max_idx].find(xor_val);
    if (it != idx_contributions[max_idx].end()) {
        idx_contributions[max_idx].erase(it);
    }

    // 更新线段树
    if (idx_contributions[max_idx].empty()) {
        update_tree(1, 1, N, max_idx, INF);
    } else {
        update_tree(1, 1, N, max_idx, *idx_contributions[max_idx].begin());
    }
}

int main() {
    // 优化 I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> N >> Q)) return 0;

    for (int i = 1; i <= N; ++i) {
        cin >> A[i];
        sorted_A.push_back({A[i], i});
    }

    // 初始排序
    sort(sorted_A.begin(), sorted_A.end());

    // 初始化线段树值为 INF
    fill(tree, tree + 4 * MAXN, INF);

    // 构建初始贡献
    for (int i = 0; i < N - 1; ++i) {
        add_contribution(sorted_A[i], sorted_A[i+1]);
    }

    for (int q = 0; q < Q; ++q) {
        int type;
        cin >> type;
        if (type == 1) {
            int i, x;
            cin >> i >> x;

            // 1. 在 sorted_A 中找到旧值 A[i]
            // 使用 lower_bound 二分查找，但因为值可能重复，需要检查 index
            pair<int, int> target = {A[i], i};
            auto it = lower_bound(sorted_A.begin(), sorted_A.end(), target);

            // lower_bound 可能找到数值相同但 index 不同的元素，必须精确匹配
            // 由于我们总是存 (val, index)，且 index 唯一，所以可以直接比较
            // 但为了保险（如果有多重集逻辑），可以用 while 循环微调，但在 vector<pair> 默认排序下是精确的。

            int idx_in_sorted = distance(sorted_A.begin(), it);

            // 2. 删除旧贡献 (与前一个，与后一个)
            if (idx_in_sorted > 0) {
                remove_contribution(sorted_A[idx_in_sorted - 1], sorted_A[idx_in_sorted]);
            }
            if (idx_in_sorted < sorted_A.size() - 1) {
                remove_contribution(sorted_A[idx_in_sorted], sorted_A[idx_in_sorted + 1]);
            }
            // 此时如果前后都有，删除后，原来的 前-后 变成了相邻，需要添加吗？
            // 答：不需要在这里添加，因为我们马上要插入新元素，打断这个连接。
            // 不，稍等。逻辑是：删除一个元素后，原来的 前 和 后 变成了相邻。
            // 但我们是“修改”，即“删除旧的，插入新的”。
            // 为了逻辑清晰，我们可以先视为“删除”，加上(前, 后)的贡献，然后再“插入”，打断。
            // 实际上直接操作 vector 比较直观：

            // 若删除位置 idx，则 idx-1 和 idx+1 变为相邻
            if (idx_in_sorted > 0 && idx_in_sorted < sorted_A.size() - 1) {
                add_contribution(sorted_A[idx_in_sorted - 1], sorted_A[idx_in_sorted + 1]);
            }

            // 从 vector 中移除
            sorted_A.erase(it);

            // 3. 插入新值
            A[i] = x;
            target = {x, i};

            // 找到新位置
            it = upper_bound(sorted_A.begin(), sorted_A.end(), target);
            idx_in_sorted = distance(sorted_A.begin(), it);

            // 插入 vector
            sorted_A.insert(it, target);

            // 处理新位置的贡献
            // 插入位置现在是 idx_in_sorted
            // 新的邻居是 idx_in_sorted-1 和 idx_in_sorted+1

            // 如果插入到了中间，原来的 (idx-1, idx+1) 不再相邻，需要移除贡献
            if (idx_in_sorted > 0 && idx_in_sorted < sorted_A.size() - 1) {
                remove_contribution(sorted_A[idx_in_sorted - 1], sorted_A[idx_in_sorted + 1]);
            }

            // 添加新贡献
            if (idx_in_sorted > 0) {
                add_contribution(sorted_A[idx_in_sorted - 1], sorted_A[idx_in_sorted]);
            }
            if (idx_in_sorted < sorted_A.size() - 1) {
                add_contribution(sorted_A[idx_in_sorted], sorted_A[idx_in_sorted + 1]);
            }

        } else {
            int r;
            cin >> r;
            // 查询前 r 个元素的最小异或
            // 即查询线段树区间 [1, r] 的最小值
            // 注意：我们的贡献是记在 max(i, j) 上的，所以只有当 i, j <= r 时，贡献才会被查询到。
            // 且我们的 multiset/SegTree 索引是 1 到 N。
            int ans = query_tree(1, 1, N, 1, r);
            cout << ans << "\n";
        }
    }

    return 0;
}
0