计蒜客41387 - XKC's basketball team

发表于 更新于 分类于 阅读次数：

题目链接：ICPC 2019 徐州赛区网络赛 E

对于每个\(a_i\)，我们要找一个最大的\(j > i\)，满足\(a_j \geq a_i + m\)。

考离线询问。对于一个点\(a_i\)，加入一个询问和一个修改——在\(i\)位置插入\(a_i\)，和一个查询——比\(a_i + m\)大的最大的\(j\)。我们可以对修改和查询进行排序，用优先队列维护比当前\(a_i + m\)大的最大的\(j\)，然后离线回答即可。

渐进时间复杂度\(O(n \log n)\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 500000 + 5;
const int UPD = 0;
const int QRY = 1;
struct Query {
    int type, val, pos;
    friend bool operator < (const Query &u, const Query &v) {
        if (u.val != v.val) return u.val > v.val;
        else if (u.pos != v.pos) u.pos > v.pos;
        else return u.type < v.type;
    }
} task[MAX_N * 2];
int n, m, a[MAX_N], ans[MAX_N];
priority_queue <int> q;
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        task[i] = {UPD, a[i], i};
        task[i + n] = {QRY, a[i] + m, i};
    }
    sort(task + 1, task + 2 * n + 1);
    // for (int i = 1; i <= 2 * n; ++i) printf("type = %d, val = %d, pos = %d\n", task[i].type, task[i].val, task[i].pos);
    for (int i = 1; i <= 2 * n; ++i) {
        if (task[i].type == UPD) {
            q.push(task[i].pos);
        } else {
            if (q.empty() || q.top() <= task[i].pos) ans[task[i].pos] = -1;
            else ans[task[i].pos] = q.top() - task[i].pos - 1;
        }
    }
    for (int i = 1; i <= n; ++i) printf("%d%c", ans[i], i == n ? '\n' : ' ');
    return 0;
}