Steven_MengのBlog

补很久以前的坑


图片来自lxl课件

显然,将每栋楼房都求一个斜率,然后发现一个楼房能被看到可以等价于它的斜率比之前的任何一个都大。

于是我们要求$\sum _{i=1}^n [a[j] \le a[i] \ for \ j \in [1,i-1]]$。

这个怎么求?

考虑我们对于区间$[l,r]$维护两个值,第一个是最大值$max$,第二个是$increase$,表示把上面的式子上边界调成$r$,下边界调成$l$的值。

$max$维护不说,如何维护$increase$?

考虑左边区间的最大值$max_l$,如果右边区间有值小于$max_l$,直接可以$pass$掉。

左边区间的$increase$可以直接加上,然后后半部分的区间我们可以$\log n$求解(加上大于$max_l$的限制)。

1
tree[i].increase=tree[i<<1].increase+query(tree[i<<1].maxn,i<<1|1);

我们再讲一讲query函数的实现:

第一种情况比较好理解,如果左边区间的所有数都小于等于限制数,则全部pass掉,进入右区间求解。

1
2
3
if (tree[i<<1].maxn<=Max){
return query(Max,i<<1|1);
}

第二种情况需要仔细思量,如果左边区间的所有数有大于限制数的,显然要进入左区间求解,但是要不要进入右区间?

不用!考虑到现在的值$increase$是左区间对右区间进行限制的值,然而左区间没有限制的值我们也计算出了,考虑到$max_l>Max$于是左区间会对右区间进行更强的限制,于是tree[i].increase-tree[i<<1].increase就是答案。

总代码:

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN 100005
using namespace std;
struct SegmentTree{
struct node{
int l,r;
double maxn;
int increase;
//区间最大值;区间最长上升序列的长度
}tree[MAXN<<2];
void build(int l,int r,int i){
tree[i].l=l;
tree[i].r=r;
tree[i].maxn=0.0;
if (l==r){
return ;
}
int mid=(l+r)>>1;
build(l,mid,i<<1);
build(mid+1,r,i<<1|1);
}
int query(double Max,int i){
if (tree[i].l==tree[i].r){
return tree[i].maxn>Max;
}
if (tree[i<<1].maxn<=Max){
return query(Max,i<<1|1);
}
else {
return query(Max,i<<1)+tree[i].increase-tree[i<<1].increase;
}
}
void update(int i,int pos,double val){
int l=tree[i].l,r=tree[i].r;
if (l==r){
tree[i].maxn=val;
tree[i].increase=1;
return ;
}
int mid=(l+r)>>1;
if (pos<=mid){
update(i<<1,pos,val);
}
else {
update(i<<1|1,pos,val);
}
tree[i].maxn=max(tree[i<<1].maxn,tree[i<<1|1].maxn);
tree[i].increase=tree[i<<1].increase+query(tree[i<<1].maxn,i<<1|1);
}
}Seg;
int main(){
int n,m;
scanf("%d%d",&n,&m);
Seg.build(1,n,1);
while (m--){
int x,y;
scanf("%d%d",&x,&y);
Seg.update(1,x,(double)y/x);
printf("%d\n",Seg.tree[1].increase);
}
}

 评论