【Codeforces】1665E MinimizOR 题解

题目大意

给定长度为 $n\ (1 \le n \le 10^5)$ 的数组，$a_i\ (0 \le a_i \le 2^{30})$，$q\ (1 \le q \le 10^5)$ 次查询，每次给定 $l, r$，在区间内任选两个数，求它们或运算后的最小值。

题目链接

思路

一个重要性质

假设都是 $k$ 位数，若要最小值那么只需要知道最小的 $k+1$ 个数就可以了，结果由它们产生，证明如下：

采用数学归纳法：

$k=1$ 时，那么所有数都是 $0, 1$ 其中一种，那么显然成立，选最小的两个数就可以成立。

假如 $n=k$ 时成立，那么对于 $n=k+1$ 时：

• 所有数第 $k+1$ 位均为 $1$，那么答案的这一位也是 $1$，所以就在剩下的位数中寻找最小的一部分数，此时子问题和 $n=k$ 时一致，故结论成立。
• 至少有两个数第 $k+1$ 位为 $0$，那么为了使得答案最小，肯定选择这一位为 $0$ 的数，在低位寻找他们之间最小的一部分数，此时子问题和 $n=k$ 时一致，故结论成立。
• 只有一个数第 $k+1$ 位为 $0$，那么答案这一位也是 $1$，然后再在剩下的位数中寻找最小的数，此时子问题和 $n=k$ 时一致。等于说是分为了两部分，一部分是仅有的一个第 $k+1$ 位为 $0$ 的数，另一部分就是剩下的位数中寻找最小的一部分数，两部分加起来，就是 $k+2$ 个。故假如 $n=k$ 时成立，那么对于 $n=k+1$ 时也成立。证明完毕。

做法

那么剩下的就简单了，给定 $l, r$ 可以用线段树维护区间最小的 $31$ 个数，也可以用主席树连续查找 $k+1$ 个第 $k+1$ 小的数。然后求最小值。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int maxN = 1e5 + 7;
int T, n, m, a[maxN], ind[maxN];
int ls[maxN << 5], rs[maxN << 5], rt[maxN << 5], tot, sum[maxN << 5], len;

inline int getId(int x)
{
    return lower_bound(ind + 1, ind + 1 + len, x) - ind;
}

int build(int l, int r)
{
    int root = ++tot;
    if(l == r)
        return root;
    int mid = (l + r) >> 1;
    ls[root] = build(l, mid);
    rs[root] = build(mid + 1, r);
    return root;
}

int update(int k, int l, int r, int root)
{
    int dir = ++tot;
    ls[dir] = ls[root]; rs[dir] = rs[root]; sum[dir] = sum[root] + 1;
    if(l == r)
        return dir;
    int mid = (l + r) >> 1;
    if(k <= mid)
        ls[dir] = update(k, l, mid, ls[dir]);
    else
        rs[dir] = update(k, mid + 1, r, rs[dir]);
    return dir;
}

int query(int u, int v, int l, int r, int k)
{
    int mid = (l + r) >> 1, x = sum[ls[v]] - sum[ls[u]];
    if(l == r)
        return l;
    if(k <= x)
        return query(ls[u], ls[v], l, mid, k);
    else
        return query(rs[u], rs[v], mid + 1, r, k - x);
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        tot = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        memcpy(ind, a, sizeof a);
        sort(ind + 1, ind + 1 + n);
        len = unique(ind + 1, ind + 1 + n) - ind - 1;
        rt[0] = build(1, len);
        for(int i = 1; i <= n; ++i)
            rt[i] = update(getId(a[i]), 1, len, rt[i - 1]);
        scanf("%d", &m);
        while(m--) {
            int l, r; scanf("%d%d", &l, &r);
            vector<int> s; int ans = 0x7f7f7f7f;
            for(int i = 1; i <= min(r - l + 1, 31); ++i)
                s.push_back(ind[query(rt[l - 1], rt[r], 1, len, i)]);
            for(int i = 0; i < s.size(); ++i)
                for(int j = i + 1; j < s.size(); ++j)
                    ans = min(ans, s[i] | s[j]);
            printf("%d\n", ans);
        }
    }
    return 0;
}