一般情况是维护序列，每次暴力找大于 \(x\) 的位置，然后减去 \(x\)，但是这样做的复杂度并没有保障。进一步可以考虑将值域分块，只有在某个数掉到下面的块时更新，剩下的打标记。
不规则的分块是处理这些问题的有效手段。可以考虑以 \(b^k\) 分块，每一块对应 \([b^k,b^{k+1})\)，那么一个数最多掉 \(\log_b n\) 次。此时，对于每一块，按照上面的做法用线段树暴力维护。
注意到一个数在一个块里最多被暴力删 \(b\) 次，同时每一个数最多往下掉 \(\log_b a_i\) 次，线段树单次操作是 \(O(\log_2 n)\) 的。那么总复杂度是 \(O((n+m+mb)\log _2n\log_ba_i)\)，此时空间复杂度为 \(O(n\log_b a_i)\)，无法通过。
这里令 \(b=16\)，在空间复杂度上，考虑如何将 \(\log_ba_i\) 抵消。这里采用的解决方法是在线段树上，不保留长度小于 \(16\) 的点，然后在叶子节点用链表维护对应下标区间的所有数。注意到 \(\log_{16}a_i\) 套入原题需要开 \(8,9\) 棵线段树，这样处理后刚好满足空间要求。
struct data_structure {
int lim;
struct node { int mi, mx, pt, cnt, tag; ll sum; } t[((N - 5) >> 2) + 50];
inline void update (int x, ll y) {
if (leaf[x]) for (int now = t[x].pt; now; now = blo[now].nxt) blo[now].val -= y;
t[x].mi -= y, t[x].mx -= y, t[x].tag += y, t[x].sum -= 1ll * t[x].cnt * y;
}
inline void pushdown (int x) {
if (t[lc].cnt) update (lc, t[x].tag);
if (t[rc].cnt) update (rc, t[x].tag);
t[x].tag = 0;
}
inline void pushup (int x) {
t[x].mi = min (t[lc].mi, t[rc].mi);
t[x].mx = max (t[lc].mx, t[rc].mx);
t[x].sum = t[lc].sum + t[rc].sum;
t[x].cnt = t[lc].cnt + t[rc].cnt;
}
void insert (int x, int l, int r, int pos, int val) {
chkmin (t[x].mi, val), chkmax (t[x].mx, val), t[x].sum += val, ++ t[x].cnt;
if (leaf[x]) {
blo[pos].val = val, blo[pos].nxt = blo[pos].lst = 0;
if (! t[x].pt) return t[x].pt = pos, void ();
for (int now = t[x].pt; now; now = blo[now].nxt)
if (! blo[now].nxt) return blo[now].nxt = pos, blo[pos].lst = now, void ();
}
if (t[x].tag) pushdown (x);
pos <= mid ? insert (lc, l, mid, pos, val) : insert (rc, mid + 1, r, pos, val);
}
void modify (int x, int l, int r, int L, int R, int val) {
if (! t[x].cnt || t[x].mx <= val) return ;
if (leaf[x]) {
t[x].mi = INF, t[x].mx = 0, t[x].sum = 0, t[x].cnt = 0;
for (int now = t[x].pt; now; now = blo[now].nxt) {
if (L <= now && now <= R && blo[now].val > val && blo[now].val - val < lim) {
sta[ ++ top] = mkp (now, blo[now].val - val);
if (blo[now].lst) blo[blo[now].lst].nxt = blo[now].nxt, blo[blo[now].nxt].lst = blo[now].lst;
else t[x].pt = blo[now].nxt, blo[blo[now].nxt].lst = blo[now].lst;
} else {
if (L <= now && now <= R && blo[now].val > val) blo[now].val -= val;
chkmin (t[x].mi, blo[now].val), chkmax (t[x].mx, blo[now].val);
t[x].sum += blo[now].val, ++ t[x].cnt;
}
}
return ;
}
if (L <= l && r <= R && t[x].mi - val >= lim) return update (x, val), void ();
if (t[x].tag) pushdown (x);
if (L <= mid) modify (lc, l, mid, L, R, val);
if (R > mid) modify (rc, mid + 1, r, L, R, val);
pushup (x);
}
ll querysm (int x, int l, int r, int L, int R) {
if (leaf[x]) {
ll ans = 0;
for (int now = t[x].pt; now; now = blo[now].nxt)
if (L <= now && now <= R) ans += blo[now].val;
return ans;
}
if (L == l && r == R) return t[x].sum;
if (t[x].tag) pushdown (x);
if (R <= mid) return querysm (lc, l, mid, L, R);
if (L > mid) return querysm (rc, mid + 1, r, L, R);
return querysm (lc, l, mid, L, mid) + querysm (rc, mid + 1, r, mid + 1, R);
}
int querymi (int x, int l, int r, int L, int R) {
if (! t[x].cnt) return INF;
if (leaf[x]) {
int ans = INF;
for (int now = t[x].pt; now; now = blo[now].nxt)
if (L <= now && now <= R) chkmin (ans, blo[now].val);
return ans;
}
if (L == l && r == R) return t[x].mi;
if (t[x].tag) pushdown (x);
if (R <= mid) return querymi (lc, l, mid, L, R);
if (L > mid) return querymi (rc, mid + 1, r, L, R);
return min (querymi (lc, l, mid, L, mid), querymi (rc, mid + 1, r, mid + 1, R));
}
int querymx (int x, int l, int r, int L, int R) {
if (! t[x].cnt) return 0;
if (leaf[x]) {
int ans = 0;
for (int now = t[x].pt; now; now = blo[now].nxt)
if (L <= now && now <= R) chkmax (ans, blo[now].val);
return ans;
}
if (L == l && r == R) return t[x].mx;
if (t[x].tag) pushdown (x);
if (R <= mid) return querymx (lc, l, mid, L, R);
if (L > mid) return querymx (rc, mid + 1, r, L, R);
return max (querymx (lc, l, mid, L, mid), querymx (rc, mid + 1, r, mid + 1, R));
}
} t[9];
void init (int x, int l, int r) {
lep (i, 0, 8) t[i].t[x].mi = INF;
if (r - l + 1 <= 16) return leaf[x] = true, void ();
init (lc, l, mid), init (rc, mid + 1, r);
}