[EZOI][1211NOI模拟赛]Lis(线段树+set)

§ 1 题意

街道上有 $n$ 个位置可用来种树,自西向东标号为 $1 \sim n$。

共 $m$ 个月,在第 $i$ 个月的开始,有以下操作之一:

  1. 在编号为 $p_i$ 的位置种植一棵高度为 $h_i$ 米的树,保证每个位置只会出现一次。
  2. 砍倒自西向东数第 $x_i$ 棵树,保证存在。

其中栽下的树木每月长高 $1$ 米,且保证任意时刻没有两棵树的高度相同

求每次操作后输出树高序列的最长上升子序列长度。

$n \leq 10^5,m \leq 10^5, p_i \leq n,1 \leq h_i \leq 10,x_i \leq 10$。


§ 2 分析

首先考虑操作 $1$,由于 $1 \leq h_i \leq 10$ 且树木每月长高 $1$ 米,故 $10$ 个月及以前种植的树一定高于当前树。

令 ${\rm LIS}_i$ 表示以位置 $i$ 的树开头的最长上升子序列长度。

考虑用队列存最后种植的 $10$ 棵树,然后以位置为下标建立线段树维护其余的 ${\rm LIS}_i$ 最大值。

在位置 $p$ 种植高度为 $h$ 的树时,先将队列中最早种植的树的 ${\rm LIS}_i$ 插入“位置线段树”,并在队列中删除;然后用“位置线段树”中的后缀 $\max$ 更新当前树,并加入队列;最后 $O(10^2)$ 暴力更新队列中的树的 ${\rm LIS}_i$ 即可。

然后考虑操作 $2$,发现删除自西向东第 $x_i$ 棵树只会影响第 $1 \sim x_i-1$ 棵树的 ${\rm LIS}_i$。

题目保证任意时刻没有高度相同的树,考虑以高度为下标建立线段树维护全局 ${\rm LIS}_i$ 最大值。

由于 $1 \leq x_i \leq 10$,我们可以在种树时直接把位置存到一个 set 里,那么删除时只需先把前 $x_i$ 棵全取出,并在“高度线段树”中先将其去除;然后把要删除的第 $x_i$ 棵在 set 和“位置线段树”中去除;最后倒序遍历前 $x_i-1$ 棵树,用“高度线段树”中的后缀 $\max$ 更新后,重新插入“高度线段树”(倒序可以保证一棵树不被前面的树更新)。

最后一定要注意细节,总时间复杂度为 $O(m\log m+10\,m\log n)​$。


§ 3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;

inline void getint(int &num){
register int ch, neg = 0;
while(!isdigit(ch = getchar())) if(ch == '-') neg = 1;
num = ch & 15;
while(isdigit(ch = getchar())) num = num * 10 + (ch & 15);
if(neg) num = -num;
}

inline void checkmax(int &a, const int &b) {if(a < b) a = b;}

int n, m, h[100005];
int q[100005], inq[100005], fr, re, lis[100005], del[100005];
int tmp[100005], cnt;
set<int> s; set<int>::iterator it;

struct Segtree{
int mx[400050];
#define lch (u << 1)
#define rch (u << 1 | 1)

inline void modify(int u, int l, int r, int p, int v){
while(l < r){
const int mid = l + r >> 1;
if(p <= mid) u = lch, r = mid; else u = rch, l = mid + 1;
}
mx[u] = v;
while(u >>= 1) mx[u] = max(mx[lch], mx[rch]);
}

int query(int u, int l, int r, int ql, int qr){
if(ql > qr) return 0;
if(l == ql && r == qr) return mx[u];
const int mid = l + r >> 1;
if(qr <= mid) return query(lch, l, mid, ql, qr);
if(ql > mid) return query(rch, mid + 1, r, ql, qr);
return max(query(lch, l, mid, ql, mid), query(rch, mid + 1, r, mid + 1, qr));
}
} P, H;

int main(){
getint(n), getint(m);
for(register int gatsu = 1; gatsu <= m; gatsu++){
int opt, p; getint(opt), getint(p);
if(opt == 1){
getint(h[p]), h[p] += m - gatsu;
s.insert(p), q[re++] = p, inq[p] = 1, del[p] = 0;
if(re - fr > 10){
if(!del[q[fr]]) P.modify(1, 1, n, q[fr], lis[q[fr]]);
inq[q[fr++]] = 0;
}
lis[p] = P.query(1, 1, n, p + 1, n) + 1, cnt = 0;
for(register int i = fr; i != re; i++) if(!del[q[i]]) tmp[++cnt] = q[i];
sort(tmp + 1, tmp + cnt + 1);
for(register int i = cnt; i; i--){
for(register int j = i + 1; j <= cnt; j++)
if(h[tmp[i]] < h[tmp[j]]) checkmax(lis[tmp[i]], lis[tmp[j]] + 1);
H.modify(1, 1, m + 10, h[tmp[i]], lis[tmp[i]]);
}
}
else{
tmp[cnt = 1] = *(it = s.begin()), H.modify(1, 1, m + 10, h[*it], 0);
for(register int i = 2; i <= p; i++) tmp[++cnt] = *++it, H.modify(1, 1, m + 10, h[*it], 0);
P.modify(1, 1, n, *it, 0), del[*it] = 1, s.erase(it);
while(--cnt){
lis[tmp[cnt]] = H.query(1, 1, m + 10, h[tmp[cnt]] + 1, m + 10) + 1;
H.modify(1, 1, m + 10, h[tmp[cnt]], lis[tmp[cnt]]);
if(!inq[tmp[cnt]]) P.modify(1, 1, n, tmp[cnt], lis[tmp[cnt]]);
}
}
printf("%d\n", H.mx[1]);
}
return 0;
}