2013腾讯马拉松初赛 ACM 小明系列问题——小明序列

[c]代码库

/*

2013腾讯马拉松初赛第4场

1002小明系列问题——小明序列
 
Time Limit: 1.0 Seconds   Memory Limit: 32768K
 

大家都知道小明最喜欢研究跟序列有关的问题了，可是也就因为这样，小明几乎已经玩遍各种序列问题了。可怜的小明苦苦地在各大网站上寻找着新的序列问题，可是找来找去都是自己早已研究过的序列。小明想既然找不到，那就自己来发明一个新的序列问题吧！小明想啊想，终于想出了一个新的序列问题，他欣喜若狂，因为是自己想出来的，于是将其新序列问题命名为“小明序列”。

提起小明序列，他给出的定义是这样的：
①首先定义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
 

*/


#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#define maxn 100010
#define mid ((t[p].l+t[p].r)>>1)
#define ls (p<<1)
#define rs (ls|1)
using namespace std;
struct tree {
    int l, r;
    int max;
} t[maxn << 2];
int max(int a, int b) {
    return a > b ? a : b;
}
void pushup(int p) {
    t[p].max = max(t[ls].max, t[rs].max);
}
void build(int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if(l == r) {
        t[p].max = 0;
        return;
    }
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(p);
}
void change(int p, int x, int val) {
    if(t[p].l == t[p].r) {
        t[p].max = val;
        return;
    }
    if(x > mid)
        change(rs, x, val);
    else
        change(ls, x, val);
    pushup(p);
}
int query(int p, int l, int r) {
    if(l > r)
        return 0;
    if(t[p].l == l && t[p].r == r) {
        return t[p].max;
    }
    if(l > mid)
        return query(rs, l, r);
    else if(r <= mid)
        return query(ls, l, r);
    else
        return max(query(ls, l, mid), query(rs, mid + 1, r));
}
struct node {
    int po;
    int num;
} a[maxn];
bool cmp(node a, node b) {
    if(a.num == b.num)
        return a.po > b.po;
    return a.num < b.num;
}
int main() {
    // freopen("dd.txt","r",stdin);
    int n, d;
    while(scanf("%d%d", &n, &d) != EOF) {
        int i;
        build(1, 1, n);
        for(i = 1; i <= n; i++) {
            scanf("%d", &a[i].num);
            a[i].po = i;
        }
        sort(a + 1, a + n + 1, cmp);
        int ans = 0;
        for(i = 1; i <= n; i++) {
            int po = a[i].po, tmp = query(1, 1, po - d - 1);
            ans = max(ans, tmp + 1);
            change(1, po, tmp + 1);
        }
        printf("%d\n", ans);
    }
    return 0;
}