Möhtəşəm Seqmentlər#12301

Möhtəşəm Seqmentlər (Həll təhlili)

Problem Müəllifi:	De3b0o
Hazırlayan:	De3b0o
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Əgər $l$ -ni düzəltsək, hər dəfə $r$ -ni artırdıqda $r - l + 1$ r-l+1 dəyəri $1$ artır və aralığın bitwise AND-i azalır və ya eyni qalır.

Bu, hər $l$ üçün yalnız bir $r$ ola biləcəyini göstərir ki, aralıq ( $l, r$ ) möhtəşəm olsun. Beləliklə, hər $i$ ( $1 \leq i \leq n$ 1 \le i \le n) üçün möhtəşəm aralığın $(i, r)$ olub olmadığını yoxlamaq üçün sadəcə ikili axtarış edə bilərik.

Bir aralığın bitwise AND-ni hesablamaq üçün hər bit üçün prefiks massivini yaradırıq.

Komplekslik $O (n \cdot lo g (n) \cdot lo g (ma x A))$ \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 << "BƏLİ" << "\n";
#define no cout << "XAHİŞ EDİRƏM" << "\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
    }
}