HDU 5489 Removed Interval

题意：求一段序列中删掉L个连续元素后的LIS。

解法：我的想法很复杂= =怎么说呢……首先用nlogn的方法求LIS得到的序列dp的第i项的意义为上升子序列所有长度为i的序列结尾元素的最小值，那么先倒着用nlogn的方法求一遍最长下降子序列记为dp1，记录每一步怎么更新的dp1，再正着求一遍最长上升子序列，每次看a[i]的时候二分的在i+k到结尾的dp1中找第一个比a[i]大的数设为dp1[pos]，所以当前枚举的答案即为以a[i]作为结尾的最长上升子序列+后一段以dp1[pos]开头的最长上升子序列……枚举1～n-l，就可以得到答案了TUT……

总之很艰辛……二分废又得找队友帮忙手写二分什么的……

另一队的人提出用线段树算LIS……真·大神= =不懂怎么转移的方程……

代码：

#include<stdio.h>

#include<iostream>

#include<algorithm>

#include<string>

#include<string.h>

#include<math.h>

#include<limits.h>

#include<time.h>

#include<stdlib.h>

#include<map>

#include<queue>

#include<set>

#include<stack>

#include<vector>

#define LL long long

int inf = 1000000005;

using namespace std;

int a[100005];

LL dp1[100005], dp2[100005];

struct node

{

    bool isnew;

    int pos;

    int pre;

}note[100005];

bool cmp(int a, int b)

{

    return a > b;

}

template <class T>

int rupper_bound(T *a, T *end, T key) {

    int n = end - a;

    if(n == 0) return INT_MAX;

    if (a[n-1] > key) return n-1;

    if (a[0] <= key) return INT_MAX;

    int l = 0, r = n - 1;

    while(r - l > 1) {

        int m = (l+r) >> 1;

        if (a[m] > key) l = m;

        else r = m;

    }

    return l;

}

int main()

{

    int T;

    scanf("%d", &T);

    int cse = 1;

    while(T--)

    {

        int n, l;

        scanf("%d%d", &n, &l);

        for(int i = 1; i <= n; i++)

            scanf("%d", &a[i]);

        a[0] = -inf;

        int max1 = 0, max2 = 0;

        for(int i = n; i > l; i--)

        {

            int pos = upper_bound(dp1, dp1 + max1, a[i], cmp) - dp1;

            if(pos == max1)

            {

                note[i].isnew = 1;

                note[i].pos = max1;

                dp1[max1++] = a[i];

            }

            else

            {

                note[i].isnew = 0;

                note[i].pos = pos;

                note[i].pre = dp1[pos];

                dp1[pos] = a[i];

            }

        }

        int ans = 0;

        LL s = -inf;

        int len = 0;

        for(int i = 1; i <= n - l + 1; i++)

        {

            int pos = rupper_bound(dp1, dp1 + max1, s);

            if(pos == INT_MAX) ans = max(ans, len);

            else ans = max(ans, pos + 1 + len);

            int x = upper_bound(dp2, dp2 + max2, a[i]) - dp2;

            if(x == max2)

            {

                len = max2 + 1;

                s = a[i];

                dp2[max2++] = a[i];

            }

            else

            {

                len = x + 1;

                s = a[i];

                dp2[x] = a[i];

            }

            if(note[i + l].isnew)

            {

                max1--;

            }

            else

            {

                dp1[note[i + l].pos] = note[i + l].pre;

            }

        }

        printf("Case #%d: %d\n", cse++, ans);

    }

    return 0;

}