有的时候确实需要确定最终的状态, 以计算出插入过程中状态的关系

懵逼的 题目

传送至 BZOJ

扯淡的 题解

我不就是想做个DP我容易嘛TUT

看到题没有任何头绪, 只能看看数据范围觉得应该是个$n\lg n$的LIS, 看到题解上写着

因为是从1到n插入的, 所以后插入的数不会对之前的LIS产生影响

也并没有联想到什么解法, 只能想到每插入一个数, 就从之前的f[]中二分一个可能的答案然后接上, 最后因为不能判断二分出的答案是否在插入位置的前面, 最后也放弃了…
然后看(参悟)了看(参悟)大佬的博客才知道 [不会对之后的答案产生影响] 的意思就是可以只求最后完成序列的LIS啊:

对于一个数a[i], 在i之前, 且比a[i]小的数(即满足二分条件的数), 一定在a[i]出现前就被插入了, 所以只要最后求一遍LIS就好了

然后我就高高兴兴想去写sb LIS, 然后发现一个问题: 插入完的序列怎么求啊
想一想插入一个数只会使这个位置之后的数的编号都++
那肯定要倒序插入了, 插入的时候把这个数之后的位置的编号–即可
那么只要维护一个区间修改单点查询的树状数组, 存储每一个位置在当前情况(即已经插入了后i个数)的编号, 然后二分插入的位置就好了

然后TTTTT…

发现二分写残了…因为有修改编号, 所以插到最后会出现几个位置的编号相同的情况, 然后就会把之前已经插入的值覆盖掉…GG
发现如果二分出的位置已经有数的话(即有多个位置的编号是当前要求的编号), 一定要选所有位置中最前面的: 否则选后面的位置 会把之后所有的编号–, 前面位置的编号不会改变, 之后将永远选不到惹

然后WAWAWAWA…和黄学长对拍了也没有发现问题…

没有关文件…

GG

沙茶的 代码

改了一天, 丑的一匹


// bzoj3173

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAXN (100000 + 5)
#define INF (0x7ffffff)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))

int a[MAXN];

struct tree
{
    int c[MAXN];
    int n;
    inline int lowbit(int x)
    {
        return (x & (-x));
    }
    void init()
    {
        for (int i = 1; i <= n; i++)
        {
            c[i] = lowbit(i);
        }
    }
    int cx(int x)
    {
        int re = 0;
        for (int i = x; i; i -= lowbit(i))
        {
            re += c[i];
        }
        return re;
    }
    void xg(int x)
    {
        for (int i = x; i <= n; i += lowbit(i))
        {
            --c[i];
        }
    }
    int ef(int x)
    {
        int le = 1;
        int ri = n + 1;
        while (le < ri)
        {
            int mid = (le + ri) >> 1;
            int dqx = cx(mid);
            if (dqx == x)
            {
                if (!a[mid])
                {
                    return mid;
                }
                else
                {
                    ri = mid;
                }
            }
            else if (dqx < x)
            {
                le = mid + 1;
            }
            else
            {
                ri = mid;
            }
        }
    }
}b;

int n;

int inp[MAXN];
int f[MAXN];
int ef(int);
void solve();
void init();
int main()
{
    freopen("in.in", "r", stdin);
    freopen("wa.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &inp[i]);
        ++inp[i];
    }
    init();
    solve();
    return 0;
}
void init()
{
    b.n = n;
    b.init();

    //int dqx[MAXN];

    for (int i = n; i >= 1; i--)
    {
        int x = b.ef(inp[i]);
        b.xg(x);

        /*for (int i = 1; i <= n; i++)
        {
            dqx[i] = b.cx(i);
        }*/

        a[x] = i;
    }
}
void solve()
{
    std::memset(f, 0x7f, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        int x = ef(a[i]);
        f[x + 1] = min(f[x + 1], a[i]);
    }
    int out[MAXN];
    int lastorder = 1;
    for (int i = 1; i <= n; i++)
    {
        if (f[i] < INF)
        {
            for (int j = lastorder; j < f[i]; j++)
            {
                out[j] = i - 1;
            }
            lastorder = f[i];
        }
        else
        {
            for (int j = lastorder; j <= n; j++)
            {
                out[j] = i - 1;
            }
            break;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        printf("%d\n", out[i]);
    }
}
int ef(int x)
{
    int re = 0;
    int le = 1;
    int ri = n + 1;
    while (le < ri)
    {
        int mid = (le + ri) >> 1;
        if (f[mid] <= x)
        {
            re = mid;
            le = mid + 1;
        }
        else
        {
            ri = mid;
        }
    }
    return re;
}

/*
3
0 0 2
*/

/*
10
0 0 2 2 0 3 0 4 3 0 
*/

By 没救的 Cansult