Problem
(1 le X_i le N,1 le Y_i le 10^9,1 le N,M le 10^5)
Solution
定义( ext{slope}(i))表示((0,0))与((i,H_i))的连线的斜率。不难发现,如果第(i)个楼要被看见,当且仅当( ext{slope}(i))是前(i)个最大的。
我们把( ext{slope}(1), ext{slope}(2),cdots, ext{slope}(n))看成一个序列。问题变成:
有一个序列,初始值都为(0)。每次支持单点修改,查询最长的以第一个开始的递增子序列长度。
考虑用线段树维护。每个节点维护这个区间的斜率最大值(Max),最长的以区间第一个开始的递增子序列长度(val)。考虑合并:
- (Max)直接左右取(max)即可
- (val)不难发现左儿子的(val)直接加,右儿子分类考虑:
如果右儿子的(Max)小于等于左儿子的(Max),那么全被挡了。
否则如果右儿子的左儿子的(Max)小于等于左儿子的(Max),那么这块全被挡了,递归计算右儿子的右儿子。
否则递归计算右儿子的左儿子,然后加上有右儿子的左儿子约束的右儿子的右儿子答案。(用右儿子val-右儿子左儿子val)
时间复杂度:(mathcal{O}(mlog^2{n}))?
# include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n,m;
struct node
{
int val;
double Max;
}T[N << 2];
double slope(int x,int y)
{
return (double)((double)(y) / (double)(x));
}
int Get_ans(int root,int l,int r,double k)
{
if(l == r) return T[root].Max > k;
int mid = (l + r) >> 1;
if(T[root << 1].Max <= k) return Get_ans(root << 1 | 1,mid + 1,r,k);
else return T[root].val - T[root << 1].val + Get_ans(root << 1,l,mid,k);
}
void update(int root,int l,int r,int x,int d)
{
if(l == r && r == x)
{
T[root].val = 1,T[root].Max = slope(l,d);
return;
}
int mid = (l + r) >> 1;
if(l <= x && x <= mid) update(root << 1,l,mid,x,d);
else update(root << 1 | 1,mid + 1,r,x,d);
T[root].Max = max(T[root << 1].Max,T[root << 1 | 1].Max);
T[root].val = T[root << 1].val + Get_ans(root << 1 | 1,mid + 1,r,T[root << 1].Max);
return;
}
void build(int root,int l,int r)
{
if(l == r) {T[root].val = 0,T[root].Max = 0.0; return;}
int mid = (l + r) >> 1;
build(root << 1,l,mid),build(root << 1 | 1,mid + 1,r);
return;
}
int main(void)
{
scanf("%d%d",&n,&m);
build(1,1,n);
while(m--)
{
int x,y; scanf("%d%d",&x,&y);
update(1,1,n,x,y);
printf("%d
",T[1].val);
}
return 0;
}