CSU 1453: 平衡序列学会线段树后必做

http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1453、

题目：给定一个大小为100000的数组，里面的数字最大也是100000。现在叫你求出一段子序列，使得他们任意两个数差的绝对值都不能超过k

其实这题的关键是数字的范围，不超过100000，这样的话，就可以用线段树整段覆盖了。记dp[i]为以这个数字为结尾的，最长的LIS的多少，开始的时候dp[i]=0，用线段树把他覆盖了。每次插入一个数a[i]的时候，都去找[a[i]-k,a[i]+k]这个区间里的dp最大值，然后修改dp[a[i]] = find()+1即可。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn = +;

struct data

{

    int L,R,mx; //每个节点，都记录一个区间[L,R]。还有记录区间总和

    int mid() {return (L + R)/;}

}SegTree[maxn<<];  //右移两位，就是*4

void built (int root,int begin,int end)

{

    SegTree[root].L = begin; SegTree[root].R = end;//覆盖区间

    if (begin == end)

    {

        SegTree[root].mx = ;  return ;

    }

    built(root<<,begin,SegTree[root].mid());

    built(root<<|,SegTree[root].mid()+,end);

    SegTree[root].mx = max(SegTree[root<<].mx,SegTree[root<<|].mx);

    return ;

}

void add (int root,int pos,int val)

{

    if (SegTree[root].L == pos && pos == SegTree[root].R)

    {

        SegTree[root].mx = val;     return ;

    }

    if (pos <= SegTree[root].mid())     add(root<<,pos,val);

    else if (pos >= SegTree[root].mid()+)     add(root<<|,pos,val);

    SegTree[root].mx = max (SegTree[root<<].mx,SegTree[root<<|].mx);

    return ;

}

//[begin,end]是要查询的区间，如果所求区间包含线段树覆盖区间，就可以返回

int find (int root,int begin,int end) //区间查询

{

    //查询[1,7]的话，左子树区间覆盖了[1,6]，也可以直接返回,左子树最大值嘛

    if (begin <= SegTree[root].L && end >= SegTree[root].R) return SegTree[root].mx; //覆盖了

    if (end <= SegTree[root].mid()) //完全在左子数

        return find(root<<,begin,end);

    else if (begin >= SegTree[root].mid() + ) //完全在右子树

        return find(root<<|,begin,end);

    else

    {

        int Lmax = find(root<<,begin,end);

        int Rmax = find(root<<|,begin,end);

        return max(Lmax,Rmax);

    }

}

void work ()

{

    built(,,maxn-);

    int n;

    int k;

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

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

    {

        int x;

        scanf ("%d",&x);

        int a = max(,x-k);

        int b = min(maxn-,x+k);

        int t = find(,a,b);

        add(,x,t+);

    }

    printf ("%d\n",find(,,maxn-));

    return ;

}

int main()

{

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    int t;

    scanf ("%d",&t);

    while(t--) work();

    return ;

}

思考：这个复杂度是nlogn的，那么我们是不是又找到了一种求LIS的nlogn算法呢？

不是，说了，这题的关键是数字的大小。不超过100000，才能用线段树这样覆盖，不然的话。是不行的。

LIS中的数组的数字是不确定的。

100000

巴特西

CSU 1453: 平衡序列学会线段树后必做

最新文章

热门文章

巴特西

CSU 1453: 平衡序列 学会线段树后必做

最新文章

热门文章

CSU 1453: 平衡序列学会线段树后必做