【Codeforces】1665E MinimizOR 题解

题目大意

给定 n ( 1 ≤ n ≤ 1 0 5 ) n(1 \le n \le 10^5) n(1≤n≤105)个数 a i ( 0 ≤ a i ≤ 2 30 ) a_i(0 \le a_i \le 2^{30}) ai​(0≤ai​≤230)。有 q ( 1 ≤ q ≤ 1 0 5 ) q(1 \le q \le 10^5) q(1≤q≤105)次询问：求 l , r l,r l,r内任选两个数，它们或运算后的最小值是多少。

题目链接

思路

一个重要性质
假设都是 k k k位数，若要最小值那么只需要知道最小的 k + 1 k+1 k+1个数就可以了，结果由它们产生，证明如下:
采用数学归纳法，
k = 1 k=1 k=1时，那么所有数都是 0 , 1 0,1 0,1其中一种，那么显然成立。选最小的两个数就可以成立。
假如 n = k n=k n=k时成立，那么对于 n = k + 1 n=k+1 n=k+1时:

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

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

代码

#include 
#include 
#include 
#include 
#include 
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;
}