Untitled
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