补很久以前的坑
图片来自lxl课件
显然，将每栋楼房都求一个斜率，然后发现一个楼房能被看到可以等价于它的斜率比之前的任何一个都大。
于是我们要求∑i=1n[a[j]≤a[i] for j∈[1,i−1]]。
这个怎么求？
考虑我们对于区间[l,r]维护两个值，第一个是最大值max，第二个是increase，表示把上面的式子上边界调成r，下边界调成l的值。
max维护不说，如何维护increase？
考虑左边区间的最大值maxl，如果右边区间有值小于maxl，直接可以pass掉。
左边区间的increase可以直接加上，然后后半部分的区间我们可以logn求解（加上大于maxl的限制）。
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是左区间对右区间进行限制的值，然而左区间没有限制的值我们也计算出了，考虑到maxl>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);
}
}
|
