首先考虑时间增长的问题，设第 \(i\) 棵树的种植时间为 \(t_i\)。
那么第 \(x\) 棵树比第 \(y\) 棵树高就是 \(h_x + (t_y - t_x) > h_y\)，也就是 \(h_x - t_x > h_y - t_y\)。
所以可以直接用 \(h_i - t_i\) 当作第 \(i\) 棵树的高度，即 \(h'_i\leftarrow h_i - t_i\)。
对于增加，考虑用上 \(h_i\le 10\) 个性质。
因为有 \(h'_i\) 互不相同，这说明 \(< h'_i\) 的树只有至多 \(9\) 颗。
记 \(f_i\) 为高度为 \(i\) 的树开头的最长上升子序列长度。
可以知道实际上只需要更改至多 \(10\) 棵树的 \(f_i\) 即可。
因为对于 \(h'_j > h'_i\) 的 \(f_j\) 因为 \(h\) 的大小关系就不可能产生改变。
于是可以考虑暴力拎出这至多 \(10\) 棵树算一下 \(f_i\) 即可。
可以用线段树优化。
对于删除，同样考虑用上 \(x\le 10\) 这个限制。
相同的，只需要暴力拎出来前 \(x\) 颗树删掉第 \(x\) 颗剩下 \(x - 1\) 颗暴力算一遍即可。
但是注意这里是下标，所以维护的是 \(g_i\) 意味下标为 \(i\) 开头的最长上升子序列的长度。
同样用线段树维护一下即可。
可以用 set 存下树的高度与下标。
时间复杂度 \(O(mk(\log n + \log m))\)，\(k\) 为 \(h_i, x_i\) 的上界，这里为 \(10\)。
#include<bits/stdc++.h>
const int maxn = 2e5 + 20;
struct segtr {
int mx[maxn * 2];
#define mid ((l + r) >> 1)
inline int index(int l, int r) {return l + r | l != r;}
inline void pushup(int l, int r) {mx[index(l, r)] = std::max(mx[index(l, mid)], mx[index(mid + 1, r)]);}
inline void upd(int x, int y, int l = 1, int r = 2e5 + 10) {
if (l == r) return mx[index(l, r)] = y, void();
x <= mid ? upd(x, y, l, mid) : upd(x, y, mid + 1, r);
pushup(l, r);
}
inline int qry(int x, int l = 1, int r = 2e5 + 10) {
if (l == r) return mx[index(l, r)];
return mid < x ? qry(x, mid + 1, r) : std::max(qry(x, l, mid), mx[index(mid + 1, r)]);
}
} T1, T2;
int H_[maxn], id_[maxn];
std::set<int> id, H;
int main() {
int n, m; scanf("%d%d", &n, &m);
for (int T = 1; T <= m; T++) {
int op; scanf("%d", &op);
if (op == 1) {
int x, h; scanf("%d%d", &x, &h);
h += m - T;
id_[h] = x, H_[x] = h;
std::vector<int> P;
while (! H.empty() && *H.begin() < h) {
int i = *H.begin();
P.push_back(i), H.erase(H.find(i)), id.erase(id.find(id_[i]));
}
for (int i : P) T1.upd(id_[i], 0), T2.upd(i, 0);
P.push_back(h);
std::reverse(P.begin(), P.end());
for (int i : P) {
int val = T1.qry(id_[i]) + 1;
T1.upd(id_[i], val), T2.upd(i, val);
}
for (int i : P) id.insert(id_[i]), H.insert(i);
} else {
int x; scanf("%d", &x);
std::vector<int> P;
while (x--) {
int i = *id.begin();
P.push_back(i), id.erase(id.find(i)), H.erase(H.find(H_[i]));
}
for (int i : P) T1.upd(i, 0), T2.upd(H_[i], 0);
P.pop_back();
std::reverse(P.begin(), P.end());
for (int i : P) {
int val = T2.qry(H_[i]) + 1;
T1.upd(i, val), T2.upd(H_[i], val);
}
for (int i : P) id.insert(i), H.insert(H_[i]);
}
printf("%d\n", T1.qry(1));
}
return 0;
}