ABC403 G 数据结构

· · 题解

题意

有 q 次询问，每次询问给你一个数 x，你需要把 x 插入到初始为空的序列 A，然后对 A 排序，求 A 奇数位置上的数的和。

强制在线。

Solution

因为我们不关心这个序列到底是啥，我们只关心和，所以我们放到值域上去做。

考虑假设你有 c 个 x，那么奇数位置上的数的和是 \left \lceil \frac{c}{2} \right \rceil \times x，同样的，偶数位置上的和也是好求的。

那么这个东西肯定可以合并，所以我们就考虑线段树。

对于每个点我都记 c,odd,even 分别表示区间内点的个数，奇数位置上的和以及偶数位置上的和。

那合并的时候我们只需要看左子树的数量是奇数还是偶数就行，然后我们算出当前点的 c,odd,even 即可。

答案就是根节点的 odd。但是值域很大，所以动态开点线段树即可。

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

const int N = 3e5 + 10, P = 1e9;

int q, cnt, rt;

struct node {
    int l, r, c;
    ll odd, even;
} tr[N * 30];

#define l(rt) tr[rt].l
#define r(rt) tr[rt].r
#define mid (l + r) / 2

void push_up(node &a, node b, node c)
{
    a.c = b.c + c.c;
    a.odd = b.odd + (b.c & 1 ? c.even : c.odd);
    a.even = b.even + (b.c & 1 ? c.odd : c.even);
}

void update(int &rt, int l, int r, int p)
{
    if (!rt) rt = ++cnt;
    if (l == r) {
        tr[rt].c++;
        tr[rt].even = 1ll * tr[rt].c / 2 * l;
        tr[rt].odd = 1ll * (tr[rt].c + 1) / 2 * l;
        return;
    }
    if (p <= mid) update(l(rt), l, mid, p);
    else update(r(rt), mid + 1, r, p);
    push_up(tr[rt], tr[l(rt)], tr[r(rt)]);
}

int main()
{
    fst
    cin >> q;
    ll la = 0;
    for (int i = 1; i <= q; i++) {
        int x; cin >> x; x = (x + la) % P + 1;
        update(rt, 1, P, x);
        cout << (la = tr[rt].odd) << "\n";
    }
    return 0;
}