Codeforces Global Round 27 D.Yet Another Real Number Problem
题目
题解:
#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;
}