P4198 楼房重建线段树 + 单调栈-白红宇的个人博客

P4198 楼房重建线段树 + 单调栈

发布日期：2021-09-25 23:57:55 浏览次数：6 分类：技术文章

本文共 1832 字，大约阅读时间需要 6 分钟。

题面有点小问题，个人感觉应该是存在一个点不相交即可。

改成存在的话，理解起来就比较简单了，就是维护每个点到 (0,0) 的斜率，从前往后做一遍单调递增栈得到的单调栈长度即为答案。不过显然需要数据结构来维护，可以考虑线段树。

修改操作的两个区间合并的时候，并不能直接合并，需要发现一些潜在的性质。

(1) 左区间的第一个点一定是要选的

(2) 左区间的最大值一定要选

知道这两点之后，那么答案就是 len( L ) + cal ( R , max_len( L ) ),cal是找右区间大于左区间最大值的单调栈长度。

在cal函数的时候，如果当前区间最大值都 <= x ，那么直接返回0即可。如果递归到叶子结点则根据情况返回 1 或 0。如果左区间的最大值 <= x ，显然左区间的都可以弹掉，递归右区间。否则的话返回递归左区间 + len(u) - len(L) ，递归左区间比较容易想到，但是为什么不需要处理右区间呢？因为如果可以递归左区间的话，那么说明左区间的最大值 > x，否则就被弹掉了，而我们两个区间的长度都已经是处理好了的，比如找个样例 4 5 6 1 2 8 ，len(u) = 4 ,len(L) = 3 ,我们在没有执行cal函数的时候，已经得到了相应长度，这里保证了两个区间选到的数中，左边选的数 < 右边选的数。那么假设 x = 5 吧，递归左区间返回1，选的这个数是6，右边选的数要保证大于6的话，就应该在 len(u) 中去掉 len(L) 即可。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)using namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=100010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;struct Node{ int l,r; int len; double mx;}tr[N<<2];void pushup(int u){ tr[u].mx=max(tr[L].mx,tr[R].mx);}int cal(int u,double x){ if(tr[u].mx<=x) return 0; if(tr[u].l==tr[u].r) return tr[u].mx>x; if(tr[L].mx<=x) return cal(R,x); else return tr[u].len-tr[L].len+cal(L,x);}void build(int u,int l,int r){ tr[u]={ l,r}; if(l==r) return; build(L,l,Mid),build(R,Mid+1,r);}void modify(int u,int l,int r,double c){ if(tr[u].l==tr[u].r) { tr[u].mx=c; tr[u].len=1; return; } if(l<=Mid) modify(L,l,r,c); else modify(R,l,r,c); pushup(u); tr[u].len=tr[L].len+cal(R,tr[L].mx);}int main(){ // ios::sync_with_stdio(false);// cin.tie(0); cin>>n>>m; build(1,1,n); while(m--) { int x,y; scanf("%d%d",&x,&y); double k=1.0*y/x; modify(1,x,x,k); printf("%d\n",tr[1].len); } return 0;}/**/

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/106980235 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：hdu 3333 Turing Tree 线段树 + 离线

下一篇：P4315 月下“毛景树” 树剖边权转点权

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章