区间最短OR查询（分块+位运算解法）

题目分析

核心问题

给定长度为 n 的序列，支持两种操作：

1. 单点修改：将指定位置元素更新为新值；
2. 区间查询：找到满足「区间 OR 和 ≥ k」的最短区间长度，无解输出 -1。

关键性质

• 按位 OR 运算具有单调性：区间越长，OR 和不会减小（新增元素的 OR 只会保留或增加原有位的 1）。
• 基于单调性，固定右端点 r 时，满足条件的最短区间一定是 [l, r]（l 尽可能大），即从 r 往左找最近的 l 使区间 OR ≥ k。

挑战

• 数据范围 n, q ≤ 5e4，暴力查询（O(n) per query）会超时，需设计 O(√n) 级别的高效算法。

核心思路

采用分块算法，将序列划分为若干块（块大小 s=300），通过「块内预处理 + 跨块合并查询」平衡修改与查询的时间复杂度：

1. 块内预处理：对每个块，提前计算块内所有可能区间的 OR 信息，支持快速查询块内最短满足条件的区间；
2. 跨块查询：从右往左遍历块，积累右侧块的位信息，合并当前块的子区间与右侧块的 OR 结果，计算跨块的最短区间；
3. 单点修改：仅重构修改元素所在的块，保证修改效率。

详细算法设计

1. 分块方式

• 块大小 s=300（兼顾修改与查询效率的经验值）；
• 块编号：blk(x) = (x-1)/s + 1（第 x 个元素所在块）；
• 块边界：bll(x) = (x-1)*s + 1（第 x 块左端点），blr(x) = min(x*s, n)（第 x 块右端点）。

2. 预处理数组说明

3. 块重构流程（rb 函数）

当块内元素修改后，需重新计算块的预处理信息，步骤如下：

1. 初始化 lst[bit]（块内当前 bit 最近出现位置）和 d[块][bit]（块内 bit 第一次出现位置）；
2. 遍历块内每个元素 i（从左到右）：
   • 更新 lst[bit]：若 a[i] 的第 bit 位为 1，则 lst[bit] = i，且未初始化时更新 d[块][bit] = i；
   • 构建 b[i]：收集所有非零 lst[bit]，排序去重（按位置从大到小，保证短区间优先）；
   • 计算 c[块][len]：对 b[i] 中的每个位置，计算以 i 为右端点、长度为 i - pos + 1 的区间 OR，更新 c[块][len] 为最大值；
3. 优化 c[块]：使 c[块][len] 单调不减（因 longer 区间 OR 不小于 shorter 区间），方便后续二分。

4. 查询流程（op=2）

查询满足 OR ≥ k 的最短区间，从右往左遍历所有块，兼顾块内和跨块情况：

1. 初始化 ans = n+1（无解标记）和 lst[bit] = 0（记录右侧块的 bit 位置）；
2. 遍历每个块（从右到左）：
   • 块内查询：利用 c[块] 数组二分查找最小 len，使 c[块][len] ≥ k，更新 ans；
   • 跨块查询：结合右侧块的 lst[bit]（已积累的 bit 信息）和当前块的 b[块右端点]（当前块的 bit 位置），计算跨块区间的 OR：
     • 若右侧无积累 bit（ttmp=0）：直接检查当前块的 b[块右端点] 组成的区间 OR 是否 ≥k，更新最短长度；
     • 若右侧有积累 bit：计算当前块子区间 OR 与右侧积累 OR 的合并结果，通过双指针找到最短跨块区间，更新 ans；
   • 更新 lst[bit]：将当前块的 d[块][bit] 纳入（左侧块查询时需用到当前块的 bit 信息）；
3. 输出结果：若 ans > n 输出 -1，否则输出 ans。

5. 修改流程（op=1）

• 直接修改 a[i] 的值；
• 重构 i 所在的块（调用 rb(blk(i))），因块内预处理信息依赖所有块内元素，修改后需重新计算。

代码解析

关键宏定义

#define blk(x) ((x-1)/s+1)  // 元素x所在块编号
#define bll(x) ((x-1)*s+1)  // 块x的左端点
#define blr(x) min(x*s,n)   // 块x的右端点

• 分块大小 s=300，平衡修改（O(sw)）和查询（O(m(log s + w²))）效率。

块重构函数（rb）

• 核心作用：重新计算块内所有预处理信息，确保修改后块内查询的正确性；
• 时间复杂度：O(s*w)（s=300，w=30），修改时仅需重构一个块，效率可控。

查询核心逻辑

• 从右往左遍历块：利用 OR 单调性，优先找到短区间；
• 块内二分：O(log s) 快速找到块内最短区间；
• 跨块双指针：O(w²) 处理跨块情况（w=30，常数极小）。

修改核心逻辑

• 单点修改后直接重构块，避免维护复杂的增量信息，实现简单且高效。

时间复杂度分析

• 修改操作：O(s*w)，s=300，w=30，单次修改约 9000 次操作，q=5e4 时总操作约 4.5e7，可接受；
• 查询操作：O(m*(log s + w²))，块数 m=n/s≈167，单次查询约 167*(9+900)=1.5e5 次操作，q=5e4 时总操作约 7.5e9？实际因常数优化（如 w² 实际运行时循环次数少），代码可通过测试；
• 整体复杂度：O(q*(sw + m(log s + w²)))，是分块算法典型的「修改 O(√n) + 查询 O(√n)」平衡。

算法标签

• 分块算法
• 位运算（按位 OR）
• 预处理
• 二分查找
• 双指针

完整代码（带注释）

#include <bits/stdc++.h>
#define KamijouTouma namespace
#define Othinus std
using KamijouTouma Othinus;
const int N = 5e4, s = 300, w = 30;  // s=分块大小，w=bit位数（2^30）
#define blk(x) ((x-1)/s+1)            // 元素x所在块编号
#define bll(x) ((x-1)*s+1)            // 块x左端点
#define blr(x) min(x*s,n)             // 块x右端点

int n, q, a[N + 5];
int lst[w + 5];  // 临时记录bit最近出现位置
// b[i][j]：以i为右端点，各bit最近出现的位置（去重排序）
// tb[i]：b[i]的有效长度
// c[块][len]：块内长度为len的区间最大OR值
// d[块][bit]：块内bit第一次出现1的位置
int b[N + 5][w + 5], tb[N + 5], c[(N + s - 1) / s + 5][s + 5], d[(N + s - 1) / s + 5][w + 5];

// 重构块x的预处理信息
void rb(int x) {
    // 初始化当前块的bit记录
    for (int i = 0; i < w; i++)
        lst[i] = d[x][i] = 0;
    // 初始化块内长度对应的最大OR值
    int block_len = blr(x) - bll(x) + 1;
    for (int i = 1; i <= block_len; i++)
        c[x][i] = 0;

    // 遍历块内每个元素，构建b[i]和c[x]
    for (int i = bll(x); i <= blr(x); i++) {
        // 更新当前元素的bit最近出现位置
        for (int j = 0; j < w; j++)
            if (a[i] >> j & 1) {
                lst[j] = i;
                if (!d[x][j])  // 记录块内该bit第一次出现的位置
                    d[x][j] = i;
            }
        // 收集非零的bit位置，构建b[i]
        tb[i] = 0;
        for (int j = 0; j < w; j++)
            if (lst[j])
                b[i][++tb[i]] = lst[j];
        // 按位置从大到小排序（优先短区间），去重
        sort(b[i] + 1, b[i] + 1 + tb[i], [](int x, int y) { return x > y; });
        tb[i] = unique(b[i] + 1, b[i] + 1 + tb[i]) - b[i] - 1;
        // 计算以i为右端点的不同长度区间OR，更新c[x]
        for (int j = 1, res = 0; j <= tb[i]; j++) {
            res |= a[b[i][j]];
            int len = i - b[i][j] + 1;
            c[x][len] = max(c[x][len], res);
        }
    }

    // 优化c[x]为单调不减（长度越长OR越大），方便二分
    for (int i = 1; i <= block_len; i++)
        c[x][i] = max(c[x][i], c[x][i - 1]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;

    // 读入初始序列
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    // 初始化所有块的预处理信息
    int total_blocks = blk(n);
    for (int i = 1; i <= total_blocks; i++)
        rb(i);

    while (q--) {
        int op;
        cin >> op;

        if (op == 1) {  // 单点修改
            int i, x;
            cin >> i >> x;
            a[i] = x;
            rb(blk(i));  // 重构所在块
        } else {  // 区间查询：找OR≥k的最短区间
            int k, ans = n + 1;
            static int tmp[w + 5], vl[w + 5], ttmp;  // tmp存储右侧bit位置，vl存储对应的OR累积
            memset(lst, 0, sizeof(lst));  // 初始化右侧bit位置记录

            cin >> k;
            if (k == 0) {  // 特殊情况：OR≥0恒成立，最短区间长度1
                cout << 1 << '\n';
                continue;
            }

            // 从右往左遍历所有块
            for (int i = total_blocks; i >= 1; i--) {
                // 1. 块内查询：二分找最小长度len使c[i][len]≥k
                int block_len = blr(i) - bll(i) + 1;
                int ps = lower_bound(c[i] + 1, c[i] + 1 + block_len, k) - c[i];
                if (ps <= block_len)
                    ans = min(ps, ans);

                // 2. 跨块查询：结合右侧块的bit信息（lst）和当前块的bit信息（b[blr(i)]）
                ttmp = 0;
                // 收集右侧块的有效bit位置（去重排序）
                for (int j = 0; j < w; j++)
                    if (lst[j])
                        tmp[++ttmp] = lst[j];
                sort(tmp + 1, tmp + 1 + ttmp);
                ttmp = unique(tmp + 1, tmp + 1 + ttmp) - tmp - 1;
                // 计算右侧块的OR累积值vl
                for (int j = 1; j <= ttmp; j++)
                    vl[j] = vl[j - 1] | a[tmp[j]];

                if (ttmp) {  // 右侧有积累的bit信息
                    for (int j = 1, res = 0, ptr = ttmp; j <= tb[blr(i)]; j++) {
                        res |= a[b[blr(i)][j]];  // 当前块子区间的OR
                        if ((res | vl[ttmp]) < k)  // 合并后仍不满足，跳过
                            continue;
                        // 双指针找最小的ptr，使res | vl[ptr] ≥k
                        while (ptr && (res | vl[ptr - 1]) >= k)
                            ptr--;
                        if (ptr)  // 跨块区间：b[blr(i)][j] ~ tmp[ptr]
                            ans = min(ans, tmp[ptr] - b[blr(i)][j] + 1);
                        else {  // 仅当前块子区间满足，无需跨块
                            ans = min(ans, blr(i) - b[blr(i)][j] + 1);
                            break;  // 后续j更大，区间更长，可break
                        }
                    }
                } else {  // 右侧无积累，仅检查当前块子区间
                    for (int j = 1, res = 0; j <= tb[blr(i)]; j++) {
                        res |= a[b[blr(i)][j]];
                        if (res >= k) {
                            ans = min(ans, blr(i) - b[blr(i)][j] + 1);
                            break;
                        }
                    }
                }

                // 3. 更新右侧bit信息：将当前块的bit第一次出现位置纳入lst
                for (int j = 0; j < w; j++)
                    if (d[i][j])
                        lst[j] = d[i][j];
            }

            // 输出结果
            cout << (ans > n ? -1 : ans) << '\n';
        }
    }
    return 0;
}