HDU 5489 Removed Interval （dp+线段树） 2015合肥网络赛

题意:

给定一个长度为
N<=105
$N&lt;=10^5$的序列 求删去长度为
0<=L<=N
$0&lt;=L&lt;=N$的序列后的
LIS
$LIS$

分析:

假设你已经会
O(nlogn)的LIS
$O(nlogn)的LIS$,
删去i
$删去i$前面连续一段长度为
L
$L$即[i−L,i−1]$[i-L,i-1]$的序列, 左边是
i−L−1
$i - L - 1$, 右边是
i
$i$, 求剩下的LIS$LIS$
首先预处理出:

f[i]:=以a[i]结尾的LIS的最大长度
$f[i]:=以a[i]结尾的LIS的最大长度$

g[i]:=以a[i]开头的LIS的最大长度
$g[i]:=以a[i]开头的LIS的最大长度$
我们可以根据
i
$i$, 找到 [0,i−L−1]$[0, i−L−1]$之间的一个值
其值小于
a[i]
$a[i]$, 而其
f[i]
$f[i]$值是最大的, 也就是
O(n2)
$O(n^2)$求LIS的思想
关键是如何快速确定在
[0,i−L−1]
$[0, i−L−1]$中, 找到这个值
我们利用线段树和离散化, 将
a[i]
$a[i]$映射到线段树上
假设
i
$i$位置对应的值是x$x$,并且其映射到线段树上对应的下标是
y
$y$
那么我们只要在线段树上查找[0,y−1]$[0,y−1]$之间的最大值
maxv
$maxv$

maxv[i]=max{f[j],j∈[0,i−L+1]∪a[j]<a[i]}
$maxv[i] = max\{f[j], j\in[0, i - L + 1] \cup a[j] &lt; a[i]\}$
其实就是
dp[i]:=
$dp[i]:=$以
a[i]
$a[i]$结尾, 删去
[i−L,i−1]
$[i-L,i-1]$长度为
L
$L$的LIS$LIS$的最大长度

dp[i]=maxv[i]+g[i],ans=max{dp[i]}
$dp[i] = maxv[i] + g[i], ans = max\{dp[i]\}$

代码:

//
//  Created by TaoSama on 2015-09-27
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, L, a[N], all[N];
int f[N], g[N], h[N];

int maxv[N << 2];
void update(int o, int v, int l, int r, int rt) {
    if(l == r) {
        maxv[rt] = max(maxv[rt], v);
        return;
    }
    int m = l + r >> 1;
    if(o <= m) update(o, v, l, m, rt << 1);
    else update(o, v, m + 1, r, rt << 1 | 1);
    maxv[rt] = max(maxv[rt << 1], maxv[rt << 1 | 1]);
}

int query(int L, int R, int l, int r, int rt) {
    if(L <= l && r <= R) return maxv[rt];
    int m = l + r >> 1, ret = -INF;
    if(L <= m) ret = max(ret, query(L, R, l, m, rt << 1));
    if(R > m) ret = max(ret, query(L, R, m + 1, r, rt << 1 | 1));
    return ret;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    int t; scanf("%d", &t);
    int kase = 0;
    while(t--) {
        scanf("%d%d", &n, &L);
        for(int i = 1; i <= n; ++i) {
            scanf("%d", a + i);
            all[i] = a[i];
        }
        sort(all + 1, all + 1 + n);
        int m = unique(all + 1, all + 1 + n) - all - 1;

        memset(h, 0x3f, sizeof h);
        for(int i = 1; i <= n; ++i) {
            int k = lower_bound(h + 1, h + 1 + n, a[i]) - h;
            f[i] = k;
            h[k] = a[i];
        }
        memset(h, 0x3f, sizeof h);
        for(int i = n; i; --i) {
            int k = lower_bound(h + 1, h + 1 + n, -a[i]) - h;
            g[i] = k;
            h[k] = -a[i];
        }

        int ans = 0;
        a[n + 1] = INF; g[n + 1] = 0;
        memset(maxv, 0, sizeof maxv);
        //delete [i-l,i-1] length:l   [0,i-l-1]->maxv
        for(int i = L + 1; i <= n + 1; ++i) {
            int o = lower_bound(all + 1, all + 1 + m, a[i]) - all;
            ans = max(ans, query(0, o - 1, 0, m, 1) + g[i]);
            o = lower_bound(all + 1, all + 1 + m, a[i - L]) - all; //插入一个新的
            if(i <= n) update(o, f[i - L], 0, m, 1);
        }
        printf("Case #%d: %d\n", ++kase, ans);
    }
    return 0;
}