2021牛客暑期多校训练营2 K(树状数组、构造)

Description

有一个排列 , 令 表示 中满足 的 的个数，现在给出 个不重复的 和 ，问能否构造一个 排列 符合条件。

Solution

(这个做法感觉比拓扑排序好理解)
显然对于每一个 ，必须满足 ，那么对于未给出数值的 ，可以考虑先给它们填充上数值，不妨令 ，这样构造能够满足的条件，随后只需要从后往前构造即可。
从后往前构造时，假如当前 ，那么最理想的情况下是 ，但是可能在前面的构造里已经填充了 等值，所以需要用一个树状数组维护前面已经用的值，再二分找到符合条件的最小数值填到当前位置。例如 ，前面已经用了 ，那么 ，构造出来的样子就是 。

Code

#include<bits/stdc++.h>

const int mod = 1e9 + 7;
const int N = 1e6 + 5;

int a[N], b[N];
bool vis[N];
int T[N];

class Bit {
    public:
    int lowbit(int x) {
        return x & (-x);
    }
    Bit() {
        memset(T, 0, sizeof(T));
    }
    void update(int x, int add) {
        while (x < N) {
            T[x] += add;
            x += lowbit(x);
        }
    }
    int query(int x) {
        int res = 0;
        while (x) {
            res += T[x];
            x -= lowbit(x);
        }
        return res;
    }
};

void solve() {
    int n, k, ok = 1; std::cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        int id, x; std::cin >> id >> x;
        b[id] = x;
        if (b[id] > id) {
            ok = 0;
        }
    }
    if (!ok) {
        std::cout << -1 << '\n'; return ;
    }
    Bit Tree;
    for (int i = 1; i <= n; i++) {
        Tree.update(i, 1);
    }
    for (int i = 1; i <= n; i++) {
        if (!b[i]) {
            b[i] = b[i - 1] + 1;
        }
        if (b[i] - b[i - 1] > 1) {
            std::cout << -1 << '\n'; return ;
        }
    }
    for (int i = n; i >= 1; i--) {
        int left = 1, right = n;
        int ans = -1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (Tree.query(mid) >= b[i]) {
                ans = mid; 
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        a[i] = ans;
        Tree.update(ans, -1);
    }
    for (int i = 1; i <= n; i++) {
        std::cout << a[i] << " \n"[i == n];
    }
}

signed main() {
    std::cin.sync_with_stdio(false), std::cin.tie(nullptr);
    int T = 1; //std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}