首页 > 其他分享 >[题解]CF1665E MinimizOR

[题解]CF1665E MinimizOR

时间:2024-06-24 12:35:12浏览次数:29  
标签:MinimizOR int 题解 CF1665E value re while 显然 res

思路

发现 \(2^k\) 大的数,最终的答案一定由前 \(k + 1\) 小的元素组成。

考虑数学归纳法,显然当 \(k = 1\) 成立。假令 \(k'\) 时成立,证明 \(k = k' + 1\) 时成立即可:

  1. 若第 \(k\) 位有两个及以上的 \(0\),显然最终答案的第 \(k\) 位一定为 \(0\),因此考虑前面的 \(k - 1\) 位,显然取前 \(k + 1\) 小的数是对的。

  2. 若第 \(k\) 位只有一个 \(0\),显然最终答案的第 \(k\) 位一定为 \(1\),因此考虑前面的 \(k - 1\) 位,显然取前 \(k + 1\) 小的数成立。

  3. 若第 \(k\) 位没有 \(0\),显然最终答案的第 \(k\) 位一定为 \(1\),考虑前 \(k - 1\) 位,显然取前 \(k + 1\) 小的数可以。

因此我们不妨使用线段树维护区间前 \(31\) 小。

Code

#include <bits/stdc++.h>
#define re register
#define int long long

using namespace std;

const int N = 1e5 + 10,inf = (int)(1e18) + 10;
int n,q;
int arr[N];
vector<int> emp;

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

struct seg{
    #define ls(u) (u << 1)
    #define rs(u) (u << 1 | 1)
    
    struct value{
        vector<int> v;

        value friend operator +(const value &a,const value &b){
            value v;
            for (auto x:a.v) v.v.push_back(x);
            for (auto x:b.v) v.v.push_back(x);
            sort(v.v.begin(),v.v.end());
            while (v.v.size() > 31) v.v.pop_back();
            return v;
        }
    };

    struct node{
        int l,r;
        value val;
    }tr[N << 2];

    inline void pushup(int u){
        tr[u].val = tr[ls(u)].val + tr[rs(u)].val;
    }

    inline void build(int u,int l,int r){
        tr[u] = {l,r,{emp}};
        if (l == r) return tr[u].val.v.push_back(arr[l]),void();
        int mid = l + r >> 1;
        build(ls(u),l,mid),build(rs(u),mid + 1,r);
        pushup(u);
    }

    inline auto query(int u,int l,int r){
        if (l <= tr[u].l && tr[u].r <= r) return tr[u].val;
        int mid = tr[u].l + tr[u].r >> 1;
        value res = {emp};
        if (l <= mid) res = res + query(ls(u),l,r);
        if (r > mid) res = res + query(rs(u),l,r);
        return res;
    }

    #undef ls
    #undef rs
}T;

inline void solve(){
    n = read();
    for (re int i = 1;i <= n;i++) arr[i] = read();
    T.build(1,1,n);
    q = read();
    while (q--){
        int l,r,ans = inf;
        l = read(),r = read();
        vector<int> res = T.query(1,l,r).v;
        int len = res.size();
        for (re int i = 0;i < len;i++){
            for (re int j = i + 1;j < len;j++) ans = min(ans,res[i] | res[j]);
        }
        printf("%lld\n",ans);
    }
}

signed main(){
    int T;
    T = read();
    while (T--) solve();
    return 0;
}

标签:MinimizOR,int,题解,CF1665E,value,re,while,显然,res
From: https://www.cnblogs.com/WaterSun/p/18264796

相关文章

  • [题解]CF1473D Program
    思路因为此题目中对于数的更新只能为\(1\),所以,如果我们找到了\([1,l-1]\)与\([r+1,n]\)中能获得的两个极值即可。我们为\(S\)赋予权值,用一个数组\(a\)储存:如果\(S_i\)为+,则其权值为\(1\)。否则其权值为\(-1\)。那么,在第\(i\)次操作后,能产生的数是\(\s......
  • [题解]CF1312E Array Shrinking
    思路本题为P3146变式,也算是一道很经典的区间DP题了。因为\(n\leq500\),考虑区间DP。定义\(dp_{i,j}\)表示操作\([i,j]\)区间剩余长度的最小值。那么,我们可以枚举一个中间值\(k\),可以显然地得到一个状态转移方程(即不能合二为一的情况):\[dp_{i,j}=\min(dp_{i,......
  • [题解]CF1223F Stack Exterminable Arrays
    CCF出的原题观摩一下。思路首先可以用一个Trie来维护。在这里对本文中的一些变量做一下说明。\(p\)表示当前维护的Trie中,指向的元素编号。\(t_i\)表示在Trie中编号为\(i\)的元素在原序列中的值。\(f_i\)表示在Trie中编号为\(i\)的元素在Trie中的父节点。......
  • [题解]CF1175E Minimal Segment Cover
    思路这是一道简单的DP题,DP题的核心就是状态转移。先来说一说\(dp\)数组的含义。\(dp_{i,j}\)表示从\(i\)这个点用\(2^j\)条线段能走到的最远的点。我们再来考虑一下边界情况。因为我们只用\(2^0\)条线段,那么:\(dp_{i,0}=\max(dp_{i,0},r)\)接着,我们递推一......
  • [题解]CF1092D1 Great Vova Wall (Version 1)
    思路发现,如果相邻元素的奇偶性相同,那么一定能通过在较低的位置竖着放若干个如果在\(i\)的位置竖着放一块砖头,使得这两列的高度相同。那么,我们想到直接考虑\(h_i\)的奇偶性,即将\(h_i\leftarrowh_i\bmod2\)。如果\(h_i=h_{i+1}\),我们显然可以同时使\(h_i\)和\(h......
  • [题解]CF1070C Cloud Computing
    思路考虑用线段树维护区间信息:价格在\([l,r]\)之间的CPU的数量。购买所有价格在\([l,r]\)之间CPU所需的钱。容易将区间修改转化为差分,从而实现单点修改。于是可以使用\(n\)个vector存储第\(i\)天所需进行的修改。查询第\(i\)天的答案时,如果不足\(k\)......
  • [题解]CF1746B Rebellion
    思路首先我们需要看到题目一个特殊的地方:这个序列中只存在\(0\)和\(1\)。那么,我们不难发现最终的答案一定是形如下面的序列:\(0,\dots,0,1,\dots,1\)。知道了这些,就很好想了。我们从后往前枚举,如果当前一位为\(0\)了,就从\(last\simi\)扫一遍,如果有\(1\)将最靠前的\(......
  • [题解]CF1742G Orray
    思路做这道题之前,首先要知道一个性质:\(a\operatorname{or}b\geqa\)。那么,我们就能得出一个结论:经过一定顺序的排列,最多经过\(\lceil\log_2^{a_{\max}}\rceil\)个数就能让前缀或的值达到最大值。我们不妨令有一个位置\(i\),\(b_1,b_2,\dots,b_{i-1}\)单调递增,而\(b_i......
  • [题解]CF1742E Scuza
    2022/11/23:修改了一下代码。题意有\(T\)组数据,每次给出一个\(n,q\),表示台阶的数量和询问的次数。然后再给出一个\(a_i\)为台阶高度的差分数组。每次询问给出一个\(k\),表示每次能走\(k\)个单位的高度。问:最高能到达的高度。思路考虑暴力,我们知道了高度的差分数组,那......
  • [题解]CF1741D Masha and a Beautiful Tree
    思路我们可以观察样例,不难发现:对于任意一段长度为\(2^k\)的区间中,如果最大值减最小值加\(1\)等于此区间的长度,那么一定有解。因为,我们的目标是使整个序列升序排列。因此,我们在一个区间内的最大值减最小值加\(1\)与区间长度是相等的。所以,我们可以用上述结论为判断无解的......