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

时间：2023-01-14 19:31:56

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

    标题链接：

    http://acm.hdu.edu.cn/showproblem.php?pid=4521

    标题意思：

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

    解题思绪：

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

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

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

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

    代码：

    每日一道理
人生好似一条河，既有波澜壮阔，汹涌澎湃，也有清风徐来，水波不兴；人生好似一首歌，既有欢乐的音符，也有悲壮的旋律；人生好似一条船，既有一帆风顺时，也有急流险滩处。愿我们都能勇于经受暴风雨的洗礼，接受生活的挑战和考验！ 
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<queue>
#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美元给程序员，转身就去睡觉了。

标签：

相关文章