solution.cpp

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5;
int a[maxn], tree[maxn << 2]; // 假设层数 M = log 2 (n - 1), 树节点数就要开2倍了
                              // 循环中遍历最后一个结点的的子节点(虽然不存在) 需要 2n * 2的数组大小
int n, maxpoint;

void init()
{
    maxpoint = 1;
    while (maxpoint < n)
        maxpoint <<= 1; //比最后一个结点大的2的倍数个结点
    memset(tree, 0, sizeof(tree));
    memset(a, 0, sizeof(a));
}

void update(int k, int addnum)
{                      // addnum 在出现前边时更新所有子节点 + 1， 出现后边时 所有子节点都 - 1
    k += maxpoint - 1; // 每个节点都当作根节点一样遍历子节点
    tree[k] += addnum;
    while (k)
    {
        k = (k - 1) >> 1; // 访问父节点直到根结点
        tree[k] += addnum;
    }
}

int query(int a, int b, int k, int l, int r)
{
    if (a == b || (r <= a || l >= b))
        return 0; // 不符合查询条件 返回 0
    if (a <= l && r <= b)
        return tree[k]; // 子区域就直接返回
    else
    {
        int mid = (l + r) >> 1;
        return query(a, b, (k << 1) + 1, l, mid) + query(a, b, (k + 1) << 1, mid, r);
    }
}

int main()
{
    int temp;
    map<int, int> mp;
    cin >> n;
    init();
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        if (mp.count(temp))
        {
            int pre = mp[temp];
            a[i] = query(pre + 1, i, 0, 0, maxpoint);
            update(pre, -1);
        }
        else
        {
            a[i] = -temp;
        }
        mp[temp] = i;
        update(i, 1);
    }
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    return 0;
}