Untitled

 avatar
unknown
plain_text
a year ago
2.6 kB
3
Indexable
/*...Bismillahir Rahmanir Rahim...*/
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;

//debug..........
#ifdef Abdul_Aziz
#include "debug.cpp"
#else
#define dbg(x...)
#endif

#define   int  long long
#define   ll   long long
#define   ld   long double
#define   pb   push_back
#define   vi   vector<int>
#define   bitcount(x)  (int)__builtin_popcount(x)
#define   Lsb(x)  (int)__builtin_ctzll(x)
#define   fast  ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define   sz(x)  (int)x.size()
#define   all(a) (a).begin(),(a).end()
#define   Yes  cout << "YES\n"
#define   No  cout << "NO\n"
#define   ff   first
#define   ss   second
#define   endl  "\n"
#define   pi   acos(-1.0)
#define   pii  pair<int,int>
#define   lcm(a,b) (a/__gcd(a, b)*b)

const int  mod = 998244353 ;
const int N = 200005 ;
const int inf = 2147483647;

inline void solve() {
    int n ; cin >> n ;
    vi g[32], a(n), pre(31, -1);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector <vi> p(n, vi(31));
    vi p1(31), p2(31);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 31; ++j) {
            if (a[i] >> j & 1) {
                p[i][j] += i - pre[j] + p1[j];
                p1[j] = p2[j];
                p2[j] = p[i][j];
                pre[j] = i;
                // position save as calculation helper
                g[j].pb(i);
            }
        }
    }

    vector <vi> s(n, vi(31));
    vi r1(31), r2(31), suf(31, n);
    for (int i = n - 1; i >= 0; --i) {
        for (int j = 0; j < 31; ++j) {
            if (a[i] >> j & 1) {
                s[i][j] += suf[j] - i + r1[j];
                r1[j] = r2[j];
                r2[j] = s[i][j];
                suf[j] = i;
            }
        }
    }
    // dbg("come");

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int bit = 30;
        while (!(a[i] >> bit & 1)) {
            --bit;
        }
        auto ii = lower_bound(all(g[bit]), i);
        // dbg(i, *ii, bit)
        // left odd + right even
        if (ii != g[bit].begin()) {
            auto c = ii;
            --c;
            // dbg(*c)
            ans += p[*c][bit] * s[i][bit];
        }
        // left even + right odd
        ++ii;
        if (ii != g[bit].end()) {
            // dbg(*ii, g[bit].back())
            ans += p[i][bit] * s[*ii][bit];
        }
        // dbg(i, ans)
    }
    cout << ans << endl;
}

signed main()
{
    // fast ;
    int t = 1 ;  cin >> t ;
    while (t--) solve() ;
    return 0 ;
}
Editor is loading...
Leave a Comment