hdu 4521 샤 오 밍 시리즈 문제 - 샤 오 밍 시퀀스 라인 트 리 간격 이 d 보다 긴 상승 서브 시퀀스

샤 오 밍 시리즈 문제 - 샤 오 밍 시퀀스
Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others) Total Submission(s): 2000    Accepted Submission(s): 610
Problem Description
샤 오 밍 은 서열 과 관련 된 문 제 를 연구 하 는 것 을 가장 좋아 한 다 는 것 을 모두 가 알 고 있 지만 그 렇 기 때문에 샤 오 밍 은 각종 서열 문 제 를 거의 다 해 보 았 다.불쌍 한 샤 오 밍 은 각 사이트 에서 새로운 서열 문 제 를 찾 고 있 지만 찾 아 다 니 는 것 은 모두 자신 이 이미 연구 한 서열 이다.샤 오 밍 은 찾 을 수 없 으 니 스스로 새로운 서열 문 제 를 발명 하 라 고 생각 했다.샤 오 밍 은 생각 하고 생각 하 다가 마침내 새로운 서열 문 제 를 생각해 냈 다. 그 는 미 친 듯 이 기뻐 했다. 자신 이 생각 한 것 이기 때문에 새로운 서열 문 제 를 '샤 오 밍 서열' 이 라 고 명명 했다.
샤 오 밍 서열 을 언급 하면 그 가 내 린 정 의 는 다음 과 같다.
① 먼저 S 를 질서 있 는 서열 로 정의 하고 S = {A1, A2, A3,..., An}, n 을 요소 갯 수 로 한다.
② 그 다음 에 Sub 를 S 에서 꺼 낸 키 시퀀스 로 정의 합 니 다. Sub = {Ai 1, Ai 2, Ai 3,..., Aim}, m 를 요소 개수 로 정의 합 니 다.
③ 그 중 하위 만족 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

      d        。

        d，     nlogn      。              ，      。     d               dp   。       ，       dp （         dp，     ），       。     i ，   i-d-1        ，                 d   。               [1,a[i]-1]     。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
using namespace std;

typedef pair<int,int> pii;

const int MAXN=100010;
const int MAXM=100010;
const int MAXNODE=4*MAXN;
const int LOGMAXN=50;
const int INF=0x3f3f3f3f;

int N,D;
int a[MAXN],dp[MAXN];

struct SegmentTree{
    int m[MAXNODE];
    void clear(){
        memset(m,0,sizeof(m));
    }
    void update(int o,int L,int R,int pos,int v){
        if(L>=R){
            m[o]=max(m[o],v);
            return;
        }
        int mid=L+(R-L)/2;
        if(pos<=mid) update(o<<1,L,mid,pos,v);
        else update(o<<1|1,mid+1,R,pos,v);
        m[o]=max(m[o<<1],m[o<<1|1]);
    }
    int query(int o,int L,int R,int ql,int qr){
        if(ql<=L&&qr>=R) return m[o];
        int mid=L+(R-L)/2;
        int ret=0;
        if(ql<=mid) ret=max(ret,query(o<<1,L,mid,ql,qr));
        if(qr>mid) ret=max(ret,query(o<<1|1,mid+1,R,ql,qr));
        return ret;
    }
}tree;

int main(){
    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&D)!=EOF){
        tree.clear();
        int MAX=-1;
        for(int i=1;i<=N;i++){
            scanf("%d",&a[i]);
            a[i]++;
            MAX=max(MAX,a[i]);
        }
        int ans=1;
        for(int i=1;i<=N;i++){
            if(i<=D+1) dp[i]=1;
            else{
                tree.update(1,1,MAX,a[i-D-1],dp[i-D-1]);
                if(a[i]>1) dp[i]=tree.query(1,1,MAX,1,a[i]-1)+1;
                else dp[i]=1;

            }
            ans=max(ans,dp[i]);
        }
        printf("%d
",ans);
    }
    return 0;
}