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;
}