题解：P6642 [CCO 2020] Exercise Deadlines

· · 题解

解析：

考虑依次填入每个位置。 最后一个位置只能填 d_i=n 的位置，第 k 个位置只能填 d_i \ge k 。

我们随着 k 的减小，决策集合扩大。

那么对于第 n 个位置，一定选择 d_i=n 中最大的 i 。依次类推，第 k 个位置肯定选择决策集合中最大的数。

需要在线维护加入一个数，查询最大值和删除最大值，直接用优先队列即可。

最后再用树状数组求出逆序对。

代码：

#include<bits/stdc++.h>
#define int long long 
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 200005
using namespace std;
int n, d[N], c[N];
vector<int>u[N];
inline void add(int x) {
    for (; x <= n; x += x & -x)c[x]++;
}
inline int ask(int x) {
    int sum = 0;
    for (; x; x -= x & -x)sum += c[x];
    return sum;
}
priority_queue<int>q;
signed main() {
    scanf("%d", &n);
    int ans = 0;
    rep(i, 1, n)scanf("%d", &d[i]), u[d[i]].push_back(i);
    pre(i, n, 1) {
        for (int j = 0; j < (int)u[i].size(); j++)q.push(u[i][j]);
        if (q.empty()) {
            puts("-1");
            return 0;
        }
        int cur = q.top();
        q.pop();
        ans += ask(cur);
        add(cur);
    }
    printf("%lld\n", ans);
    return 0;
}

完结撒花，谢谢