hdu 4521 线段树改点求点的应用

时间:2023-03-09 16:21:14
hdu    4521  线段树改点求点的应用

小明系列问题——小明序列

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 1264    Accepted Submission(s): 344

Problem Description
  大家都知道小明最喜欢研究跟序列有关的问题了,可是也就因为这样,小明几乎已经玩遍各种序列问题了。可怜的小明苦苦地在各大网站上寻找着新的序列问题,可是找来找去都是自己早已研究过的序列。小明想既然找不到,那就自己来发明一个新的序列问题吧!小明想啊想,终于想出了一个新的序列问题,他欣喜若狂,因为是自己想出来的,于是将其新序列问题命名为“小明序列”。
  提起小明序列,他给出的定义是这样的:   ①首先定义S为一个有序序列,S={ A1 , A2 , A3 , ... , An },n为元素个数 ;   ②然后定义Sub为S中取出的一个子序列,Sub={ Ai1 , Ai2 , Ai3 , ... , Aim },m为元素个数 ;   ③其中Sub满足 Ai1 < Ai2 < Ai3 < ... < Aij-1 < Aij < Aij+1 < ... < Aim ;   ④同时Sub满足对于任意相连的两个Aij-1与Aij都有 ij - ij-1 > d (1 < j <= m, d为给定的整数);   ⑤显然满足这样的Sub子序列会有许许多多,而在取出的这些子序列Sub中,元素个数最多的称为“小明序列”(即m最大的一个Sub子序列)。   例如:序列S={2,1,3,4} ,其中d=1;   可得“小明序列”的m=2。即Sub={2,3}或者{2,4}或者{1,4}都是“小明序列”。
  当小明发明了“小明序列”那一刻,情绪非常激动,以至于头脑凌乱,于是他想请你来帮他算算在给定的S序列以及整数d的情况下,“小明序列”中的元素需要多少个呢?
Input
  输入数据多组,处理到文件结束;   输入的第一行为两个正整数 n 和 d;(1<=n<=10^5 , 0<=d<=10^5)   输入的第二行为n个整数A1 , A2 , A3 , ... , An,表示S序列的n个元素。(0<=Ai<=10^5)
Output
  请对每组数据输出“小明序列”中的元素需要多少个,每组测试数据输出一行。
Sample Input
2 0
1 2
5 1
3 4 5 1 2
5 2
3 4 5 1 2
Sample Output
2
2
1
百度上的结题报告都是按值来建树,只找到一篇按下标建树的,看了之后感觉好巧妙,记录输入序列里面每一个元素的下标id,首先将序列从小到大排序,对于权值相同的作如下处理:
假如题目要求的序列相邻两个元素可以相等,那么按id从小到大排列,否则按从大到小排列,然后对于排序后的序列,一边插入,一边查询。
代码:
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=;
#define L(x) 2*x
#define R(x) 2*x+1
struct node
{
int l,r,mx;
int mid(){return (l+r)>>;}
}tree[*maxn];
struct NODE
{
int val,id;
}pp[maxn];
bool cmp(NODE a,NODE b)
{
if(a.val==b.val)return a.id>b.id;
return a.val<b.val;
}
void pushup(int p)
{
tree[p].mx=max(tree[L(p)].mx,tree[R(p)].mx);
}
void build(int p,int l,int r)
{
tree[p].l=l;
tree[p].r=r;
tree[p].mx=;
if(l==r)return;
int m=tree[p].mid();
build(L(p),l,m);
build(R(p),m+,r);
pushup(p);
}
void update(int p,int pos,int val)
{
if(tree[p].l==tree[p].r)
{
tree[p].mx=max(tree[p].mx,val);
return;
}
int m=tree[p].mid();
if(pos<=m)update(L(p),pos,val);
else update(R(p),pos,val);
pushup(p);
}
int query(int p,int l,int r)
{
if(l>r)return ;
if(tree[p].l>=l&&tree[p].r<=r)return tree[p].mx;
int m=tree[p].mid();
int ans=-;
if(l<=m)ans=max(ans,query(L(p),l,r));
if(r>m)ans=max(ans,query(R(p),l,r));
return ans;
}
int main()
{
int i,j,k,m,n,d;
while(~scanf("%d%d",&n,&d))
{
for(i=;i<=n;i++)scanf("%d",&pp[i].val),pp[i].id=i;
sort(pp+,pp+n+,cmp);
// for(i=1;i<=n;i++)cout<<pp[i].val<<" ";cout<<endl;
build(,,n);
int ans=;
for(i=;i<=n;i++)
{
j=pp[i].id;
k=query(,,j-d-);
ans=max(ans,k+);
update(,j,k+);
}
printf("%d\n",ans);
}
return ;
}