【线段树】[Luogu P4198]楼房修建

显然要维护斜率区间单调递增

并且第一个必选，后一个比前一个选中的斜率大的必选

考虑如何合并两个区间

我们维护一个least值，least这个值必选，且之后选的都必须严格大于least，Push_Up的时候就像在线段树上二分一样做就好了

这样每次Push_Up是$logn$的，线段树单点修改时$logn$的，所以总复杂度是$O(nlog^2n)$的，再维护一个区间最大值可以做到一些不必要但是可以卡常的剪枝...

 #include<bits/stdc++.h>

 #define writeln(x)  write(x),puts("")

 #define writep(x)   write(x),putchar(' ')

 using namespace std;

 inline int read(){

     int ans=,f=;char chr=getchar();

     while(!isdigit(chr)){if(chr=='-') f=-;chr=getchar();}

     while(isdigit(chr)){ans=(ans<<)+(ans<<)+chr-;chr=getchar();}

     return ans*f;

 }void write(int x){

     if(x<) putchar('-'),x=-x;

     if(x>) write(x/);

     putchar(x%+'');

 }const int M = 2e5+;

 int s[M<<],n,T;

 double mx[M<<],a[M];

 #define ls (i<<1)

 #define rs (i<<1|1)

 #define mid (l+r>>1)

 inline int Push(int i,int l,int r,double least){

     if(mx[i]<=least) return ;

     if(a[l]>least) return s[i];

     if(l==r) return a[l]>least;

     if(mx[ls]<=least) return Push(rs,mid+,r,least);

     return Push(ls,l,mid,least)+s[i]-s[ls];

 }inline void Push_Up(int i,int l,int r){

     mx[i]=max(mx[ls],mx[rs]);

     s[i]=s[ls]+Push(rs,mid+,r,mx[ls]);

 }void Update(int i,int l,int r,int pos,double x){

     if(l==r)return mx[i]=x,s[i]=,void();

     if(pos<=mid) Update(ls,l,mid,pos,x);

     else Update(rs,mid+,r,pos,x);

     Push_Up(i,l,r);

 }int main(){

     n=read(),T=read();

     while(T--){

         int x=read(),y=read();

         a[x]=y*1.0/(x*1.0);

         Update(,,n,x,y*1.0/(1.0*x));

         printf("%d\n",s[]);

     }return ;

 }

巴特西

【线段树】[Luogu P4198]楼房修建

最新文章

热门文章