【CS Round 34】Max Or Subarray

【题目链接】:https://csacademy.com/contest/round-34/summary/

【题意】



让你找一个最短的连续子串;

使得这个子串里面所有数字or起来最大;

【题解】



对于每一个起点i;

最大值肯定是i..n这一段全部or起来;

只是长度可能还能再短一点;

而且,是有单调性的;

定义一个右端点;

显然,你可以二分右端点;

右端点越靠右,i..右端点这一段or起来就会越大;

因为1的数量只会不下降.

处理出前i个数所有数二进制位在某一位的1的个数的前缀和就好;(30位)



【Number Of WA】



1



【反思】



一开始没注意到为0的情况;

初始化的答案长度应该设置为+oo;



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 1e5+100;

LL g[N][40],a[N],two[40],temp[40],tma = 0,tlen = N;

int n;

int main(){

    //Open();

    Close();

    cin >> n;

    two[0] = 1;

    rep1(i,1,30)

        two[i] = two[i-1]*2;

    rep1(i,1,n) cin >> a[i];

    rep1(i,1,n){

        rep1(j,0,29){

            g[i][j] = g[i-1][j];

            if ( two[j] & a[i]){

                g[i][j]++;

            }

        }

    }

    rep1(i,1,n){

        LL ma = 0;

        rep1(j,0,29){

            temp[j] = g[n][j]-g[i-1][j];

            if (temp[j])

                ma+=two[j];

        }

        int l = i,r = n,idx = n;

        while (l <= r){

            int mid = (l+r)>>1;

            LL tt = 0;

            rep1(j,0,29){

                temp[j] = g[mid][j]-g[i-1][j];

                if (temp[j])

                    tt+=two[j];

            }

            if (tt < ma){

                l = mid + 1;

            }else{

                idx = mid;

                r = mid - 1;

            }

        }

        if (ma>tma){

            tma = ma,tlen = idx-i+1;

        }

        else

            if (ma==tma && tlen > idx-i+1){

                tlen = idx-i+1;

            }

    }

    //cout << tma << endl;

    cout << tlen << endl;

    return 0;

}