AT_abc340_e 题解

yyrwlj · 2024-02-11 19:58:28 · 个人记录

思路

考虑使用支持区间加和单点查询的线段树维护。

对于每一个操作，先查询当前盒子内的球有多少个，设有 x 个，然后将该位置清零。

然后先看能加几圈，也就是 \lfloor \frac{x}{n} \rfloor 是多少。

把这些圈加上后，看剩下部分加的区间是什么即可。

Code

#include <iostream>
using namespace std;
const int N = 200005;
typedef long long LL;
LL w[N << 2], tag[N << 2];
int n, m;
inline void pushup(int u)
{
    w[u] = w[u << 1] + w[u << 1 | 1];
}
void build(int u,int l,int r)
{
    if (l == r)
    {
        scanf("%lld", &w[u]);
        return;
    }
    int mid = (l + r) >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void maketag(int u,int l,int r,LL k)
{
    tag[u] += k;
    w[u] += k * (r - l + 1);
}
void pushdown(int u,int l,int r,int mid)
{
    maketag(u << 1, l, mid, tag[u]);
    maketag(u << 1 | 1, mid + 1, r, tag[u]);
    tag[u] = 0;
}
void update(int u,int l,int r,int L,int R,int x)
{   
    if (L <= l && r <= R)
    {
        maketag(u, l, r, x);
        return;
    }
    int mid = (l + r) >> 1;
    if (tag[u])
        pushdown(u, l, r, mid);
    if (L <= mid)
        update(u << 1, l, mid, L, R, x);
    if (mid < R)
        update(u << 1 | 1, mid + 1, r, L, R, x);
    pushup(u);
}
LL query(int u,int l,int r,int x)
{
    if (l == r)
        return w[u];
    int mid = (l + r) >> 1;
    if (tag[u])
        pushdown(u, l, r, mid);
    if (x <= mid)
        return query(u << 1, l, mid, x);
    return query(u << 1 | 1, mid + 1, r, x);
}
void update1(int u,int l,int r,int x)
{
    if (l == r)
    {
        w[u] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    if (tag[u])
        pushdown(u, l, r, mid);
    if (x <= mid)
        update1(u << 1, l, mid, x);
    else
        update1(u << 1 | 1, mid + 1, r, x);
    pushup(u);
}
void change(int l,int r)
{
    if (l > n)
    {
        l -= n;
        r -= n;
    }
    if (r <= n)
        update(1, 1, n, l, r, 1);
    else
    {
        update(1, 1, n, l, n, 1);
        update(1, 1, n, 1, r - n, 1);
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while (m--)
    {
        int x;
        scanf("%d", &x);
        x ++;
        LL ai = query(1, 1, n, x);
        update1(1, 1, n, x);
        if (ai >= n)
            update(1, 1, n, 1, n, ai / n);
        ai %= n;
        if (ai)
            change(x + 1, x + ai);
    }
    for (int i=1;i<=n;i++)
        printf("%lld ", query(1, 1, n, i));
    return 0;
}