2019ICPC南京网络赛F Greedy Sequence

题意：对于1<=i<=n每次找到(pos[i]-k,pos[i]+k)内不大于i的最大那个数，ans[i]=ans[mx]+1，若ans[mx]未知则递归处理ans[mx]

PS：这个题比赛时写主席树k前驱没剪枝T了，然而实验室里的同学n^2过10w...自闭

主席树k前驱：在[l，r]范围内找到比k小的最大值，本质是带剪枝的主席树树上dfs

主要算法思想：当前区间[l，r]的sum（数字个数）为0则剪枝，l==r时，如果l<k说明l是k的前驱，否则说明不存在k的前驱，查找时，如果k<=m+1(m=(l+r)/2)或者右区间不存在数字（数字个数为0）时，返回递归求左区间的答案（注意为什么是m+1，因为当k<=m+1时，小于k的值必定只可能出现在左区间[l,m]中），否则查找右区间，当递归右区间有解，则必为最优解，直接返回这个解即可，当右区间无解，才继续递归左区间求解

这样一系列剪枝以后，这个算法就可以跑的很快了！

其实还有个想法就是二分第k大值去求，这个思路比较简单而且复杂度是O(nlogn^2)，不知道会不会T，有时间了尝试补上

AC代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+;

struct Node

{

    int l,r,sum;

}node[N*];//nlogn

int cnt;

int a[N],root[N];

void Insert(int l,int r,int pre,int& now,int val)

{

    node[++cnt]=node[pre];

    now=cnt;

    node[now].sum++;

    if(l==r)return;

    int m=(l+r)>>;

    if(val<=m)Insert(l,m,node[pre].l,node[now].l,val);

    else Insert(m+,r,node[pre].r,node[now].r,val);

}

int query(int L,int R,int l,int r,int k)

{

    if(node[R].sum-node[L].sum==)return -;

    if(l==r)return l<k?l:-;

    int m=(l+r)>>;

    if(k<=m+||node[node[R].r].sum-node[node[L].r].sum==)return query(node[L].l,node[R].l,l,m,k);

    int t=query(node[L].r,node[R].r,m+,r,k);

    if(t!=-)return t;

    return query(node[L].l,node[R].l,l,m,k);

}

int n,k;

int pos[N],dp[N];

int solve(int i)

{

    if(dp[i]!=-)return dp[i];

    int l=max(,pos[i]-k);

    int r=min(n,pos[i]+k);

    int res=query(root[l-],root[r],,n,i);

    if(res==-)return dp[i]=;

    return dp[i]=solve(res)+;

}

int main() {

    ios::sync_with_stdio(false);

    cin.tie();

    cout.tie();

    int T;

    cin>>T;

    while (T--) {

        cnt=;

        memset(dp,-, sizeof(dp));

        memset(node,, sizeof(node));

        cin >> n >> k;

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

            cin >> a[i];

            pos[a[i]]=i;

        }

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

            Insert(, n, root[i - ], root[i], a[i]);

        }

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

        {

            solve(i);

            cout<<dp[i]<<(i==n?'\n':' ');

        }

    }

    return ;

}

巴特西

2019ICPC南京网络赛F Greedy Sequence

最新文章

热门文章