区间加与异或和查询实现

问题需求：支持区间加法操作，查询区间内元素异或和的后m位（m≤10）。序列长度1e5，操作数1e5。

解决方案：采用线段树结合bitset优化。建立1024位bitset存储区间内数值分布的奇偶性，区间加法通过循环位移实现。当区间长度小于128时切换为暴力计算以优化常数。

const int BIT_RANGE = 1024;
const int BLOCK_SIZE = 128;

struct SegmentNode {
    bitset<BIT_RANGE> bit_data;
    int shift_tag = 0;
};

SegmentNode tree[4 * MAXN];
int base_arr[MAXN];

void merge_nodes(int parent) {
    tree[parent].bit_data = tree[left_child(parent)] ^ tree[right_child(parent)];
}

void apply_shift(int node, int shift_val) {
    shift_val &= BIT_RANGE - 1;
    tree[node].bit_data = (tree[node].bit_data << shift_val) | 
                          (tree[node].bit_data >> (BIT_RANGE - shift_val));
    tree[node].shift_tag += shift_val;
}

void propagate(int node) {
    if (!tree[node].shift_tag) return;
    apply_shift(left_child(node), tree[node].shift_tag);
    apply_shift(right_child(node), tree[node].shift_tag);
    tree[node].shift_tag = 0;
}

void build_tree(int node, int left, int right) {
    if (right - left + 1 <= BLOCK_SIZE) {
        for (int idx = left; idx <= right; ++idx)
            tree[node].bit_data.flip(base_arr[idx]);
        return;
    }
    int mid = (left + right) >> 1;
    build_tree(left_child(node), left, mid);
    build_tree(right_child(node), mid + 1, right);
    merge_nodes(node);
}

void update_range(int node, int left, int right, int start, int end, int add_val) {
    if (right - left + 1 <= BLOCK_SIZE) {
        int low = max(left, start);
        int high = min(right, end);
        for (int idx = low; idx <= high; ++idx) 
            tree[node].bit_data.flip((base_arr[idx] + tree[node].shift_tag) & (BIT_RANGE-1));
        for (int idx = low; idx <= high; ++idx) 
            base_arr[idx] += add_val;
        for (int idx = low; idx <= high; ++idx) 
            tree[node].bit_data.flip((base_arr[idx] + tree[node].shift_tag) & (BIT_RANGE-1));
        return;
    }
    if (left >= start && right <= end) 
        return apply_shift(node, add_val);
    propagate(node);
    int mid = (left + right) >> 1;
    if (start <= mid) update_range(left_child(node), left, mid, start, end, add_val);
    if (end > mid) update_range(right_child(node), mid + 1, right, start, end, add_val);
    merge_nodes(node);
}

bitset<BIT_RANGE> query_range(int node, int left, int right, int start, int end) {
    bitset<BIT_RANGE> result;
    if (right - left + 1 <= BLOCK_SIZE) {
        int low = max(left, start);
        int high = min(right, end);
        for (int idx = low; idx <= high; ++idx)
            result.flip((base_arr[idx] + tree[node].shift_tag) & (BIT_RANGE-1));
        return result;
    }
    if (left >= start && right <= end)
        return tree[node].bit_data;
    propagate(node);
    int mid = (left + right) >> 1;
    if (start <= mid) result ^= query_range(left_child(node), left, mid, start, end);
    if (end > mid) result ^= query_range(right_child(node), mid + 1, right, start, end);
    return result;
}

区间连通块数量查询实现

问题需求：维护动态集合，支持插入/删除操作，查询包含指定元素的连通块大小（相邻元素差值≤k视为连通）。

解决方案：离散化后建立线段树，节点记录区间左右边界、元素总数和连通块数量。查询时通过二分确定连通块边界。

struct SegmentInfo {
    long min_val, max_val;
    int element_count, component_count;
};

SegmentInfo combine_segments(const SegmentInfo &a, const SegmentInfo &b) {
    if (a.element_count == 0) return b;
    if (b.element_count == 0) return a;
    long new_min = min(a.min_val, b.min_val);
    long new_max = max(a.max_val, b.max_val);
    int total_elements = a.element_count + b.element_count;
    int merge_adjust = (max(a.min_val, b.min_val) - min(a.max_val, b.max_val) <= k) ? 1 : 0;
    return { new_min, new_max, total_elements, 
             a.component_count + b.component_count - merge_adjust };
}

void update_tree(int node, int left, int right, int pos, int delta) {
    if (left == right) {
        tree[node].min_val = tree[node].max_val = values[pos];
        tree[node].element_count += delta;
        tree[node].component_count += delta;
        return;
    }
    int mid = (left + right) >> 1;
    if (pos <= mid) update_tree(left_child(node), left, mid, pos, delta);
    else update_tree(right_child(node), mid + 1, right, pos, delta);
    tree[node] = combine_segments(tree[left_child(node)], tree[right_child(node)]);
}

SegmentInfo query_segment(int node, int left, int right, int ql, int qr) {
    if (ql <= left && qr >= right) return tree[node];
    int mid = (left + right) >> 1;
    if (qr <= mid) return query_segment(left_child(node), left, mid, ql, qr);
    if (ql > mid) return query_segment(right_child(node), mid + 1, right, ql, qr);
    return combine_segments(
        query_segment(left_child(node), left, mid, ql, qr),
        query_segment(right_child(node), mid + 1, right, ql, qr)
    );
}

int find_left_bound(int pos) {
    int low = 1, high = pos;
    while (low <= high) {
        int mid = (low + high) >> 1;
        SegmentInfo seg = query_segment(1, 1, n, mid, pos);
        if (seg.component_count == 1) {
            high = mid - 1;
            count_cache = seg.element_count;
        } else low = mid + 1;
    }
    return count_cache;
}

int find_right_bound(int pos) {
    int low = pos, high = n;
    while (low <= high) {
        int mid = (low + high) >> 1;
        SegmentInfo seg = query_segment(1, 1, n, pos, mid);
        if (seg.component_count == 1) {
            low = mid + 1;
            count_cache = seg.element_count;
        } else high = mid - 1;
    }
    return count_cache;
}

int main() {
    // 离散化处理
    vector<long> all_values;
    for (int i = 0; i < m; ++i) {
        cin >> ops[i] >> data[i];
        all_values.push_back(data[i]);
    }
    sort(all_values.begin(), all_values.end());
    all_values.erase(unique(all_values.begin(), all_values.end()), all_values.end());
    
    // 建立线段树
    for (int i = 0; i < m; ++i) {
        int pos = lower_bound(all_values.begin(), all_values.end(), data[i]) - all_values.begin() + 1;
        if (ops[i] == INSERT) {
            state[pos] = !state[pos];
            update_tree(1, 1, n, pos, state[pos] ? 1 : -1);
        } else {
            int right_part = find_right_bound(pos);
            int left_part = find_left_bound(pos);
            cout << (left_part + right_part - 1) << endl;
        }
    }
}