CF264E Roadside Trees <线段树>

Problem

Roadside Trees

$\mathrm{Time\;limit:\;5\;Sec}$
$\mathrm{Memory\;limit:\;256\;MB}$

Description

Squirrel Liss loves nuts. Liss asks you to plant some nut trees.
There are $n$ positions (numbered 1 to $n$ from west to east) to plant a tree along a street. Trees grow one meter per month. At the beginning of each month you should process one query. The query is one of the following types:

• Plant a tree of height $h$ at position $p$.
• Cut down the $x^{th}$ existent (not cut) tree from the west (where $x$ is 1-indexed). When we cut the tree it drops down and takes all the available place at the position where it has stood. So no tree can be planted at this position anymore.

After processing each query, you should print the length of the longest increasing subsequence. A subset of existent trees is called an increasing subsequence if the height of the trees in the set is strictly increasing from west to east (for example, the westmost tree in the set must be the shortest in the set). The length of the increasing subsequence is the number of trees in it.
Note that Liss don’t like the trees with the same heights, so it is guaranteed that at any time no two trees have the exactly same heights.

Input

The first line contains two integers: $n$ and $m$ $(1\le n\le 10^5; 1\le m\le 2\cdot 10^5)$ – the number of positions and the number of queries.
Next $m$ lines contains the information of queries by following formats:

• If the $i^{th}$ query is type 1, the $i^{th}$ line contains three integers: 1, $p_i$, and $h_i$ $(1\le p_i\le n,1\le h_i\le 10)$, where $p_i$ is the position of the new tree and $h_i$ is the initial height of the new tree.
• If the $i^{th}$ query is type 2, the $i^{th}$ line contains two integers: 2 and $x_i$ $(1\le x_i\le 10)$, where the $x_i$ is the index of the tree we want to cut.
  The input is guaranteed to be correct, i.e.,
• For type 1 queries, $p_i$ will be pairwise distinct.
• For type 2 queries, $x_i$ will be less than or equal to the current number of trees.
• At any time no two trees have the exactly same heights.

In each line integers are separated by single spaces.

Output

Print $m$ integers – the length of the longest increasing subsequence after each query. Separate the numbers by whitespaces.

Example

Input

4 6
1 1 1
1 4 4
1 3 4
2 2
1 2 8
2 3

Output

1
2
3
2
2
2

标签：线段树

Translation

有一条有$n$ $(n\le10^5)$个位置的路，现有$m$ $(m\le 2\cdot10^5)$个操作，分为两种：

1. 在第$p$ $(p\le n)$个位置种下一棵高度为$h$ $(1\le h\le 10)$的树
2. 砍掉从左向右第$x$ $(1\le x\le10)$棵树

每个单位时间内，树会长高$1$米。
每次操作后，输出当前最长上升子序列的长度。
数据保证任意时刻没有两棵树高度相同。

Solution

由于$n$比较大，显然不能用二维树状数组/线段树维护$\mathrm{DP}$。

考虑最长上升子序列如何$\mathrm{DP}$。从后往前$\mathrm{DP}$，每次找到后面的数值比当前大的位置，选出其中$\mathrm{DP}$值最大的加$1$，作为当前位置的$\mathrm{DP}$值。找后面符合条件的最大$\mathrm{DP}$值可以用线段树维护。如果将位置和数值作为$x,y$值放到坐标系上，发现如果将$x,y$值对换后，问题是完全相同的。于是可以得到另一种$\mathrm{DP}$方法：从数值最大的向数值最小的$\mathrm{DP}$，每次找到比其大的数值中对应位置在其后面的数对应的$\mathrm{DP}$值的最大值，将最大值加$1$作为当前数的$\mathrm{DP}$值。同样地，这种方法也可以用线段树维护。

观察题目中的特殊条件，发现$h,x$均不大于$10$。如果插入一棵高度为$h$的树，则需要将所有高度小于$h$的树的$\mathrm{DP}$值重新计算；如果砍掉第$x$棵树，则需要将第$1\sim (x-1)$棵树的$\mathrm{DP}$值重新计算。每次重新计算的位置均不大于$10$个。

考虑维护两棵线段树，分别对应前面的两种$\mathrm{DP}$方式（第一棵按$x$从大到小算，第二棵按$y$从大到小算）。种树时，找出所有高度小于$h$的位置，将第一棵线段树中对应位置的$\mathrm{DP}$值清零，按高度从大到小排序，然后依次计算$\mathrm{DP}$值，由于$\mathrm{DP}$到每个位置时，比它高的树都已经被$\mathrm{DP}$过了，所以可以保证正确性。砍树时，找出第$1\sim(x-1)$棵树，将第二棵线段树中对应高度的$\mathrm{DP}$值清零，从后向前依次计算$\mathrm{DP}$值，正确性同样可以保证。注意修改$\mathrm{DP}$值时在两棵线段树上都需要修改。
为了快速找到前$(x-1)$棵树，可以维护一个堆，存储当前有树的位置，每次弹出前$(x-1)$小即可。

总时间复杂度$O(10\times n\log{n})$。

附上官方题解

Code

#include <bits/stdc++.h>
#define MAX_N 200010
#define mid ((s+t)>>1)
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, mx, tr[2][MAX_N<<2];
int h[MAX_N+5], id[MAX_N+5];
priority_queue <int> heap; stack <int> sta;
void modify(int num, int v, int s, int t, int p, int x) {
    if (s == t) {tr[num][v] = x; return;}
    if (p <= mid) modify(num, v<<1, s, mid, p, x);
    if (p >= mid+1) modify(num, v<<1|1, mid+1, t, p, x);
    tr[num][v] = max(tr[num][v<<1], tr[num][v<<1|1]);
}
int query(int num, int v, int s, int t, int l, int r) {
    if (s >= l && t <= r) return tr[num][v]; int ret = 0;
    if (l <= mid) ret = max(ret, query(num, v<<1, s, mid, l, r));
    if (r >= mid+1) ret = max(ret, query(num, v<<1|1, mid+1, t, l, r));
    return ret;
}
int main() {
    read(n), read(m), mx = m+10;
    for (int now = 1; now <= m; now++) {
        int opt, p, x; read(opt), read(p);
        if (opt == 1) {
            read(x), x = x-now+m;
            h[p] = x, id[x] = p, heap.push(-p);
            for (int i = 1-now+m; i < x; i++)
                if (id[i]) modify(0, 1, 1, mx, id[i], 0);
            for (int i = x, c; i >= 1-now+m; i--) if (id[i])
                c = query(0, 1, 1, mx, id[i], mx)+1, 
                modify(0, 1, 1, mx, id[i], c), 
                modify(1, 1, 1, mx, i, c);
        }
        if (opt == 2) {
            for (int i = 1; i < p; i++)
                sta.push(-heap.top()), heap.pop(), 
                modify(1, 1, 1, mx, h[sta.top()], 0);
            p = -heap.top(), heap.pop();
            modify(0, 1, 1, mx, p, 0);
            modify(1, 1, 1, mx, h[p], 0);
            id[h[p]] = 0, h[p] = 0;
            for (int i, c; !sta.empty(); )
                i = sta.top(), 
                c = query(1, 1, 1, mx, h[i], mx)+1, 
                modify(0, 1, 1, mx, i, c), 
                modify(1, 1, 1, mx, h[i], c), 
                heap.push(-sta.top()), sta.pop();
        }
        printf("%d\n", tr[0][1]);
    }
    return 0;
}