题目大意：

是男人就下一般层。。。没什么可以多说的吧。

注意只能垂直下落。

思路分析：

后面求最大值的过程很容易想到是一个dp的过程 。

因为每一个plane 都只能从左边 从右边下两种状态。

然后我们所需要处理的问题就是 ，你如何能快速知道往左边下到哪里，往右边下到哪里。

这就是线段树的预处理。

讲线段按照高度排序。

然后按照高度从小到大加入到树中。

然后去寻找左端点 和 右端点最近覆盖的线段的编号。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e #define mid ((s+e)>>1) #define maxn 100005 using namespace std; struct Line { int h,st,ed,v; bool operator < (const Line &cmp)const { return h
      
       =e){ cov[num]=val; return; } pushdown(num); if(l<=mid)update(lson,l,r,val); if(r>mid)update(rson,l,r,val); } int dp[maxn]; int main() { int n; while(scanf("%d",&n)!=EOF) { int m=0;n++; scline[1].h=0,scline[1].st=1,scline[1].ed=maxn-1,scline[1].v=0; for(int i=2;i<=n;i++) { scanf("%d%d%d%d",&scline[i].h,&scline[i].st,&scline[i].ed,&scline[i].v); } m=maxn-1; sort(scline+1,scline+1+n); memset(cov,0,sizeof cov); for(int i=1;i<=n;i++) { ldn[i]=query(1,1,m,scline[i].st); rdn[i]=query(1,1,m,scline[i].ed); update(1,1,m,scline[i].st,scline[i].ed,i); } for(int i=1;i
       
        =1;i--) { if(dp[i]>0)dp[ldn[i]]=max(dp[ldn[i]],dp[i]+scline[ldn[i]].v); if(dp[i]>0)dp[rdn[i]]=max(dp[rdn[i]],dp[i]+scline[rdn[i]].v); } if(dp[1]>0)printf("%d\n",dp[1]); else puts("-1"); } return 0; }