题目
题解：
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define fi first
#define se second
#define lson p << 1
#define rson p << 1 | 1
#define ll long long
#define pii pair<int, int>
#define ld long double
const int maxn = 1e6 + 5, inf = 1e9, maxm = 4e4 + 5, base = 337;
const int N = 1e6;
const int mod = 1e9 + 7;
// const int mod = 998244353;
// const __int128 mod = 212370440130137957LL;
int n, m;
int a[maxn], b[maxn];
pii t[maxn << 2];
void push_up(int p){t[p] = max(t[lson], t[rson]);
}
void build(int p, int l, int r){if(l == r){t[p] = {a[l], l};return;}int mid = (l + r) >> 1;build(lson, l, mid);build(rson, mid + 1, r);push_up(p);
}
void update(int p, int l, int r, int pos, int val){if(l == r){t[p] = {val, l};return;}int mid = (l + r) >> 1;if(pos <= mid) update(lson, l, mid, pos, val);else update(rson, mid + 1, r, pos, val);push_up(p);
}
pii query(int p, int l, int r, int L, int R){if(L <= l && R >= r){return t[p];}int mid = (l + r) >> 1;pii res;if(L <= mid) res = max(res, query(lson, l, mid, L, R));if(R >= mid + 1) res = max(res, query(rson, mid + 1, r, L, R));return res;
}
int qpow(int a, int b){int res = 1;while(b){if(b & 1) res = 1LL * res * a % mod;a = 1LL * a * a % mod;b >>= 1;}return res;
}
void solve(){ll res = 0;// int k, q, w, d, p;cin >> n;// vector<int> a(n + 1), b(n + 1);vector<ll> prea(n + 1), ids, preb(n + 1);for(int i = 1; i <= n; i++){cin >> a[i];int x = a[i];b[i] = 0;while(x % 2 == 0){x /= 2;b[i]++;}a[i] = x;prea[i] = prea[i - 1] + a[i];preb[i] = preb[i - 1] + b[i];}build(1, 1, n);for(int i = 1; i <= n; i++){if(b[i]){ids.pb(i);}map<int, int> mp;int p1 = 0, p2 = 0;// cout << i << '\n';for(int j = (int)ids.size() - 1; j >= 0; j--){int id = ids[j];auto [mx, pos] = query(1, 1, n, id, i);// cout << "id = " << id << ' ' << "mx = " << mx << ' ' << "pos = " << pos << '\n';mp[pos] += b[id];int p = mp[pos];if(((__int128)a[pos] << p) > inf){p1 = id - 1;p2 = pos;break;}update(1, 1, n, pos, a[pos] << p);}if(p2){mp[p2] += preb[p1];}ll sum = prea[i] % mod;for(auto [x, y] : mp){sum = (sum + 1LL * (qpow(2, y) - 1 + mod) % mod * a[x] % mod) % mod;update(1, 1, n, x, a[x]);}cout << sum << " \n"[i == n];}
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout << fixed << setprecision(9);int T = 1;cin >> T;while (T--){solve();}return 0;
}
