题目链接：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; } |
说点什么