题意
给定 $n$ 个数,编号为 $1$ 到 $n$。$m$ 次操作,每次操作给定一个 $x$,询问编号最小的大于等于 $x$ 的数。若没有则输出 $0$,若有则输出位置,并将该位置上的数减去 $x$。
$1 \leq n, m \leq 2 \times 10^5$
题解
这里提供两个做法。
做法 1
大力分块。每次暴力循环遍历每个块,直到找到一个块,使得这个块中的最大值大于等于 $x$。
然后在这个块里遍历,找到那个位置。然后这个位置上的数减去 $x$,暴力更新块内最大值。
时间复杂度:$\mathcal O\left(m \sqrt n\right)$
代码:
constexpr tp Hat_N = 2e5 + 3, Hat_SQN = 321;
tp a[Hat_N], bid[Hat_N], bans[Hat_SQN], bl[Hat_SQN], br[Hat_SQN], btag[Hat_SQN];
void STRUGGLING([[maybe_unused]] unsigned TEST_NUMBER) {
tp n, m, B; bin >> n >> m; B = sqrt(n) + .5;
for (tp i = 1; i <= n; ++i) {
bid[i] = (i - 1) / B + 1;
if (!bl[bid[i]]) bl[bid[i]] = i;
br[bid[i]] = i;
bin >> a[i];
bans[bid[i]] = max(bans[bid[i]], a[i]);
}
while (m--) {
tp x, loc = -1; bin >> x;
for (tp i = 1; i <= bid[n]; ++i) {
if (bans[i] >= x) { loc = i; break; }
}
if (loc == -1) { bin << "0 "; continue; }
for (tp i = bl[loc]; i <= br[loc]; ++i) {
if (a[i] >= x) {
bin << i << ' ';
a[i] -= x; bans[loc] -= x;
for (tp j = bl[loc]; j <= br[loc]; ++j) bans[loc] = max(bans[loc], a[j]);
break;
}
}
}
bin << '\n';
}
做法 2
线段树二分。这个很模版,但是没有分块好写(