题意

在 1∼n 的位置能种树，刚开始能种树。 第 i 个时刻会有操作：

1. 在一个没种过树的位置 p_i 种一颗高度为 h_i 的树。
2. 砍掉第 x_i(x_i\leq 10) 棵树，保证这个位置以后不会种树。 每天树会长高 1 。 每执行一次操作，输出最长上升子序列长度。 任意时刻树的高度不同。

思路

由题意，容易观察到：对于每一个 1 操作，最多只有 9 棵树的高度小于新种的树的高度；对于每一个 2 操作，最多只有 9 棵树的下标小于新种的树的下标。我们把每棵树都看作二维平面上的一个点 (p, h)，其横坐标 p 表示这棵树的下标，纵坐标 h 表示这颗树的高度。为了方便处理，我们把 i 时刻种的树的高度加上 m-i 。

我们对每个点维护从它开始的最长上升子序列长度。这么处理后，一个点会从他右上方的点（即横、纵坐标都大于它的点）转移。对于每次操作，最多有 10 个点（包括新加入/删除的点）的值会改变。于是我们可以维护两棵线段树，分别维护横坐标和纵坐标。若要插入一个点，那么就在维护纵坐标的线段树上暴力把这 10 个点的值清零，然后询问比新加入的点高的点的最大值来计算这个点的答案，最后再依次更新其它点的答案；若要删除一个点，则在维护横坐标的线段树上操作。每次操作后，都要在另一棵线段树上修改那些值被改变的点。于是在只需要在这两棵线段树维护单点修改和区间询问最大值。单次操作复杂度为 O(10logn) 。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
const int MAXN=220000;
struct SegmentTree
{
    struct Node
    {
        int l, r;
        int cnt, val;
    } tr[4*MAXN];
    int d[MAXN];
    #define lc (x<<1)
    #define rc (x<<1|1)
    inline void cov(int x, int k)
    {
        tr[x].val=k; tr[x].cnt=k!=0?1:0;
    }
    inline void pushup(int x)
    {
        tr[x].val=max(tr[lc].val, tr[rc].val);
        tr[x].cnt=tr[lc].cnt+tr[rc].cnt;
    }
    void build(int x, int l, int r)
    {
        tr[x].l=l; tr[x].r=r;
        if (tr[x].l==tr[x].r)
        { cov(x, 0); d[tr[x].l]=0; return; }
        int mid=l+r>>1;
        build(lc, l, mid);
        build(rc, mid+1, r);
        pushup(x);
    }
    void update(int x, int p, int k)
    {
        if (tr[x].l==tr[x].r) { cov(x, k); return; }
        int mid=tr[x].l+tr[x].r>>1;
        if (p<=mid) update(lc, p, k);
        else update(rc, p, k);
        pushup(x);
    }
    int kth(int x, int k)
    {
        if (k>tr[x].cnt) return 0;
        if (tr[x].l==tr[x].r) return tr[x].l;
        if (k<=tr[lc].cnt) return kth(lc, k);
        else return kth(rc, k-tr[lc].cnt);
    }
    int query(int x, int l, int r)
    {
        if (tr[x].l>r||tr[x].r<l) return 0;
        if (l<=tr[x].l&&tr[x].r<=r) return tr[x].val;
        return max(query(lc, l, r), query(rc, l, r));
    }
    #undef lc
    #undef rc
} tp, th;
int main()
{
//  freopen("B.in", "r", stdin);
//  freopen("B.out", "w", stdout);
    int n, m, c;
    scanf("%d%d", &n, &m); c=m;
    tp.build(1, 1, n); th.build(1, 1, m+9);
    while (c--)
    {
        int op;
        scanf("%d", &op);
        if (op==1)
        {
            int p, h, k=0;
            int s[10], v[10];
            scanf("%d%d", &p, &h);
            for (int i=1; i<=9; i++)
            {
                int t=th.kth(1, i);
                if (!t||t>h+c) break;
                s[++k]=th.d[t]; v[k]=th.query(1, t, t);
                tp.update(1, th.d[t], 0);
            }
            tp.d[p]=h+c; th.d[h+c]=p;
            int w=tp.query(1, p+1, n)+1;
            tp.update(1, p, w); th.update(1, tp.d[p], w);
            for (int i=k; i>=1; i--)
            {
                w=tp.query(1, s[i]+1, n)+1;
                tp.update(1, s[i], w);
                th.update(1, tp.d[s[i]], w);
            }
        }
        else
        {
            int k, s[10];
            scanf("%d", &k);
            for (int i=1; i<k; i++)
            {
                int t=tp.kth(1, i);
                s[i]=tp.d[t]; th.update(1, tp.d[t], 0);
            }
            int h=tp.d[tp.kth(1, k)];
            th.update(1, h, 0); tp.update(1, th.d[h], 0);
            for (int i=k-1; i>=1; i--)
            {
                int w=th.query(1, s[i]+1, m+9)+1;
                th.update(1, s[i], w);
                tp.update(1, th.d[s[i]], w);
            }
        }
        printf("%d\n", tp.tr[1].val);
    }
    return 0;
}