526互联

Codeforces Round 907 (Div. 2) B. Deja Vu（二分+后缀和+位运算）

发布时间 2023-11-01 21:18:07作者: ikunhuaji

Codeforces Round 907 (Div. 2) B. Deja Vu

思路：

预处理31位的 \(2^x\) 存在\(tmp_i\)

对于输入\(a_i\)，通过查找最后一个二进制1位置，存在\(x0_i\)

由题意可知，对于输入的\(x\)，如果有\(a_i\)可整除\(x\)，则会使\(a_i\)加上\(2^{x-1}\)

所以之后除非是\(x-1\)，否则无效，因此把输入\(x\)保存降序部分在vector

\(x\)从后往前，将\(2^{x_i}\)后缀和存在sum

对于\(a_i\)，二分查找在\(x\)的第一个小于等于\(x0_i\)的位置

\(a_i\)加上后缀和

#define int long long
#define ld long double
#define pb push_back
#define pf push_front

using namespace std;

int t;
int tmp[32];
int a[100010];
int x0[100010];
vector<int>x;
deque<int>sum;

void ini()
{
    tmp[0] = 1;
    for (int i = 1; i <= 31; i++)
    {
        tmp[i] = tmp[i - 1] * 2LL;
    }
}

void ss(int f, int i)
{
    int cnt = 0;
    while (f)
    {
        if (f & 1)
        {
            x0[i] = cnt;
            return;
        }

        cnt++;
        f >>= 1;
    }
}

int check(int f)
{
    int l = 0, r = x.size() - 1;

    while (l < r)
    {
        int mid = (l + r) >> 1;

        if (x[mid] > f)
        {
            l = mid + 1;
        }
        else r = mid;
    }
    return sum[r];
}

void solve()
{
    x.clear();
    sum.clear();
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];

        ss(a[i], i);
    }

    for (int i = 1; i <= q; i++)
    {
        int z;
        cin >> z;
        if (!x.size() || x[x.size() - 1]>z)
        {
            x.pb(z);
        }
    }

    for (int i = x.size()-1; i>=0; i--)
    {
        if (i == x.size() - 1)
        {
            sum.pf(tmp[x[i]-1]);
        }
        else
        {
            sum.pf(tmp[x[i] - 1] + sum.front());
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (x0[i]>=x[x.size()-1])
        {
            a[i] += check(x0[i]);
        }
        cout << a[i] << " ";
    }
    cout << endl;
}

signed main()
{
    ini();
    //t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}