树线段线段树（端点更新） hdu-4521 小明系列问题—

树线段线段树（端点更新） hdu-4521 小明系列问题——小明序列

阅读量：6902 次

发布时间：2019-06-27

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

工作之余抽点时间出来写写博文，希望对新接触的朋友有帮助。今天在这里和大家一起学习一下树线段

标题链接：

标题意思：

求出相邻位置之差大于d的最长递增子序列的长度。

解题思绪：

由于n有10^5，用一般的dp，算法时间复杂度为o(n^2),肯定会超时。

所以用线段树进行优化。线段树维护的是区间内包含某点的最大满意条件的长度，叶子节点以该元素结尾，最长长度。

至于相邻两项隔d个位置，求dp[i]时，我们只把dp[i-d-1]更新至线段树中，然后在这颗线段树中找最大的个数，这也是线段树的一个很主要的应用方面。

线段树的功能：查找区间内最大值的优化。

代码：

每日一道理

人生好似一条河，既有波澜壮阔，汹涌澎湃，也有清风徐来，水波不兴；人生好似一首歌，既有欢乐的音符，也有悲壮的旋律；人生好似一条船，既有一帆风顺时，也有急流险滩处。愿我们都能勇于经受暴风雨的洗礼，接受生活的挑战和考验！

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #define eps 1e-6#define INF (1<<30)#define PI acos(-1.0)using namespace std;#define lson l,m,rt<<1#define rson m+1,r,(rt<<1)|1#define N (int)(1e5+5)int num[4*N],save[N],dp[N];void pushup(int rt) //向上更新{ num[rt]=max(num[rt<<1],num[rt<<1|1]); return ;}void build(int l,int r,int rt){ num[rt]=0; if(l==r) return ; int m=(l+r)>>1; build(lson); build(rson); return ;}void update(int t,int v,int l,int r,int rt) //端点更新{ if(l==r) { num[rt]=max(num[rt],v); return ; } int m=(l+r)>>1; if(t<=m) update(t,v,lson); else update(t,v,rson); pushup(rt);}int query(int L,int R,int l,int r,int rt)//找出L,R区间内最大的长度{ if(L<=l&&R>=r) return num[rt]; int m=(l+r)>>1; int Max=0; if(L<=m) Max=max(Max,query(L,R,lson)); if(R>m) Max=max(Max,query(L,R,rson)); return Max;}int main(){ int n,d; while(scanf("%d%d",&n,&d)!=EOF) { int Max=0; for(int i=1;i<=n;i++) { scanf("%d",&save[i]); Max=max(Max,save[i]); } build(0,Max,1); int ans=0; for(int i=1;i<=n;i++) { if(i-d-1>=1) update(save[i-d-1],dp[i-d-1],0,Max,1); //这是关键，只把i-d-1前面的更新至线段树中 if(save[i]==0) dp[i]=1; else dp[i]=query(0,save[i]-1,0,Max,1)+1; ans=max(dp[i],ans); } printf("%d\n",ans); } return 0;}

文章结束给大家分享下程序员的一些笑话语录：打赌

飞机上，一位工程师和一位程序员坐在一起。程序员问工程师是否乐意和他一起玩一种有趣的游戏。工程师想睡觉，于是他很有礼貌地拒绝了，转身要睡觉。程序员坚持要玩并解释说这是一个非常有趣的游戏："我问你一个问题，如果你不知道答案，我付你5美元。然后你问我一个问题，如果我答不上来，我付你5美元。"然而，工程师又很有礼貌地拒绝了，又要去睡觉。　　程序员这时有些着急了，他说："好吧，如果你不知道答案，你付5美元；如果我不知道答案，我付50美元。"果然，这的确起了作用，工程师答应了。程序员就问："从地球到月球有多远？"工程师一句话也没有说，给了程序员5美元。　　现在轮到工程师了，他问程序员："什么上山时有三条腿，下山却有四条腿？"程序员很吃惊地看着工程师，拿出他的便携式电脑，查找里面的资料，过了半个小时，他叫醒工程师并给了工程师50美元。工程师很礼貌地接过钱又要去睡觉。程序员有些恼怒，问："那么答案是什么呢？"工程师什么也没有说，掏出钱包，拿出5美元给程序员，转身就去睡觉了。

转载地址：http://rvpdl.baihongyu.com/

你可能感兴趣的文章

python to_excel参数解释_pandas中read_excel() 和 to_excel()各参数详解