cf1665E

题目大意

给定\(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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/04/18/cf1665E/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！