[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=62609346
向大(hei)佬(e)势力学(di)习(tou)
下意识的想到暴力的做法，但一看数据范围就方了。没有思路的情况下可以从数据分析入手。10^5，数据结构的大小。然而什么数据结构可以维护这样的数据呢？已学的知识里面都好像不能，那就需要新思路了
其实这是一个另类的线段树
首先要明确的是此题要求的是与（0,0）点的斜率递增，而不是高度，为了偷懒，以下的高度均指斜率
我们每次update的时候需重新统计该段的可被见的楼房数量。显然不是简单的子树相加。我们需要进行如下讨论：
(明确：h该区间的最高高度，sum该区间的可见数）
1、ls->h >= rs->h ，直接返回 ls->sum；
2、ls->h < rs->h，左子树的可见楼房都可见，而右子树就还需要求，在此新引入一个函数query( rs , ls->h )查询右子树中高度大于ls->h的可见数
针对query（Node *nd , int maxh）函数：
1、如果 ls->h <= maxh ，那么左子树的楼房都不可见，继续query（nd->rs , maxh）：
2、如果 ls->h > maxh，说明左子树的部分楼房可见，我们要继续查询左子树。那右子树呢? nd->sum - nd->ls->sum 即是。
下面详细讲一下为什么右子树的可见数为 nd->sum - nd->ls->sum
1、为什么不可以调用query（rs ，…）。如果每次都两部分都查找下去的话，很显然，这和直接暴力for一边统计没什么两样，甚至更慢。我们使用数据结构是希望把复杂度降到 log ，只query一次就可以保证查询次数是线段树的深度——logN
2、为什么就是nd->sum - nd->ls->sum。因为我们现在查询到的已经在之前update过了，sum是可以保证正确的。该区间可见数sum减去左子树区间的sum，可得出比左子树的h高的右子树的楼房数量。这个地方maxh都小于ls->h了，nd->sum - nd->ls->sum 自然是右子树可见数。
复杂度o（M*log^2 N）
代码
因为把le，ri传错了，wa了好久
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100000+5;
int n,m;
struct Node{
Node *ls,*rs;
int sum;
double h;
}*root,*null,pool[2*N],*tail=pool;
Node *newnode(){
Node *rt=++tail;
rt->ls=rt->rs=null;
rt->sum=rt->h=0;
return rt;
}
Node *build(int le,int ri){
Node *rt=newnode();
if(le==ri){
return rt;
}
int mid=(le+ri)>>1;
rt->ls=build(le,mid);
rt->rs=build(mid+1,ri);
return rt;
}
int query(Node *nd,double val,int le,int ri){
if(le==ri) return nd->h <= val ? 0 : 1 ;
int mid=(le+ri)>>1;
if(nd->ls->h <= val) return query(nd->rs,val,mid+1,ri);
else return query(nd->ls,val,le,mid) + nd->sum - nd->ls->sum ;
}
int update(Node *nd,int le,int ri){
if(nd->ls->h >= nd->rs->h) return nd->ls->sum;
else return nd->ls->sum+query(nd->rs,nd->ls->h,(le+ri)>>1+1,ri);//就在这里wa的
}
void modify(Node *nd,int le,int ri,int x,double val){
if(le==ri&&le==x){
nd->h=val;
nd->sum= val>0 ? 1 : 0;
return ;
}
int mid=(le+ri)>>1;
if(x<=mid) modify(nd->ls,le,mid,x,val);
else modify(nd->rs,mid+1,ri,x,val);
nd->sum=update(nd,le,ri);
nd->h=max(nd->ls->h,nd->rs->h);
return ;
}
int main(){
null=++tail;
null->ls=null->rs=null;
null->sum=null->h=0;
scanf("%d%d",&n,&m);
root=build(1,n);
int x,y;
while(m--){
scanf("%d%d",&x,&y);
modify(root,1,n,x,(double)y/(double)x);
printf("%d\n",root->sum);
}
return 0;
}总结：
1、线段树可以维护的不只是区间和一类的东西，它还可以有各种各样神奇的灵活的变式。这次算是开阔眼界，长知识了。
2、对线段树降低复杂度的原理有了更深刻的认识。