Majestic Segments#12301
Sign in

Majestic Segments (Editorial)

Problem Author:

De3b0o

Prepared by:

De3b0o

Edited by:

Hasan Saleh (MathModel)

Solution

If we fix , each time we increase the value r-l+1 increases by and the bitwise AND of the range decreases or stays the same.

That means for each there can only be one where the range () is majestic. So we can just binary search for each (1 \le i \le n) to check if there's a majestic range .

To calculate the bitwise AND of a range we make a prefix array for each bit.

Complexity \mathcal{O}(n \cdot \log(n) \cdot \log(maxA)).


#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define in insert
#define pb push_back
#define d3 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define cans cout << ans << "\n";
#define yes cout << "YES" << "\n";
#define no cout << "NO" << "\n";
#define pll pair<ll, ll>
#define lin cout << "\n";
#define mid ((l + r) / 2)
#define lc (2 * x)
#define rc (2 * x + 1)
#define double long double

using namespace std;

const ll N = 2e5+9;

ll n;
ll a[N];
ll bt[N][32];

ll an(ll l , ll r)
{
    ll sum = 0;
    for(ll j = 0 ; 32>j ; j++)
    {
        ll w = (1LL<<j);
        ll e = bt[r][j]-bt[l-1][j];
        if(e==r-l+1)
            sum+=w;
    }
    return sum;
}

int main()
{
    d3
    ll T = 1;
    cin >> T;
    while(T--)
    {
        cin >> n;
        for(int i = 1 ; n>=i ; i++)
        {
            cin >> a[i];
            for(ll j = 0 ; 32>j ; j++)
            {
                ll w = (1LL<<j);
                bt[i][j]=0;
                if(a[i]&w)
                    bt[i][j]=1;
            }
        }
        for(int j = 0 ; 32>j ; j++)
        {
            for(int i = 1 ; n>=i ; i++)
                bt[i][j]+=bt[i-1][j];
        }
        ll ans=0;
        for(int i = 1 ; n>=i ; i++)
        {
            ll l = i , r = n;
            ll id=0;
            while(l<=r)
            {
                if(mid-i+1-an(i,mid)<0)
                    l=mid+1;
                else if(mid-i+1-an(i,mid)>0)
                    r=mid-1;
                else
                {
                    id=mid;
                    break;
                }
            }
            if(id)
                ans++;
        }
        cans
    }
}