bzoj4282 慎二的随机数列树状数组求LIS + 构造

首先，我们不难发现N个位置都选一定不会比少选任意几个差，所以我们就先设定我们将这N个修改机会都用上，那么如果点 i">ii 前有sumv">sumvsumv个可修改点要被选的话，当前点被选择的条件是减掉sumv">sumvsumv后依然能和前面已减掉过sumv">sumvsumv的进行匹配。

Code：

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn = 100000 + 4;

int p, maxv[maxn], tags[maxn], nums[maxn], val[maxn];

inline int lowbit(int t)

{

    return t & (-t);

}

inline void update(int x,int delta)

{

    while(x <= p + 2)

        maxv[x] = max(maxv[x], delta), x += lowbit(x);

}

inline int query(int x)

{

    int ans = 0;

    while(x > 0) ans = max(ans, maxv[x]) , x -= lowbit(x);

    return ans;

}

int main()

{

    freopen("calligraphy9.in","r",stdin);

    //freopen("calligraphy.","w",stdout);

    int n, cnt = 0, sumv = 0, ans = 0, fin = 0;

    scanf("%d",&n);

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

    {

        char g[10];

        scanf("%s",g);

        if(g[0] == 'N')

        {

            tags[i] = 1;

            ++sumv;

            continue;

        }

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

    }

    ans = sumv;

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

    {

        if(tags[i]) --sumv;

        else val[i] -= sumv;

    }

    for(int i = 1;i <= n; ++i)if(!tags[i]) nums[++cnt] = val[i];

    sort(nums + 1, nums + 1 + cnt);

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

        if(!tags[i])

        {

            val[i] = lower_bound(nums + 1, nums + 1 + cnt, val[i]) - nums;

            p = max(p, val[i]);

        }

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

    {

        if(tags[i]) continue;

        int u = val[i];

        int pre = query(u - 1);

        fin = max(fin, pre + 1);

        update(u, pre + 1);

    }

    printf("%d",ans + fin);

    fclose(stdin);

    return 0;

}

巴特西

bzoj4282 慎二的随机数列树状数组求LIS + 构造

最新文章

热门文章

巴特西

bzoj4282 慎二的随机数列 树状数组求LIS + 构造

最新文章

热门文章

bzoj4282 慎二的随机数列树状数组求LIS + 构造