P3971 [TJOI2014] Alice and Bob

· · 题解

P3971 [TJOI2014] Alice and Bob

挺奇妙一贪心，思路很流畅，一步步来分析。

首先发现序列 x 如果如果是个排列答案更优，如果有重复元素，那我们找到一个前面已经有过的数字，把他前面所有数都加一，原来的 b 序列肯定不会更劣，又因为题目保证至少可以由一个排列得到，所以我们用排列分析。

然后因为 a 序列对应的 x 排列不唯一，所以我们尝试找到最优的那个排列，然后算出 b 来即可。

这里贪心的想就是越往后的数越小越好，这里严谨证明不是很会，感性理解吧，然后找一找性质。

由性质一和性质二可得 a_i 的转移在满足 j < i 且 a_j = a_i - 1 的 j 中，从最靠后的那个转移是一定可行的，由此可以发现每个数都有一个转移前驱，很容易联想到树，然后从前驱向当前点连边，对于 a_i = 1 的点建个虚点 0 方便后续遍历。

至此我们得到了一颗树，如果你按加边顺序倒序遍历一遍后，会发现得到了一个序列 x，而他就是我们想要的答案，在上面求个 b 数组就是答案了。

至于证明，我看其他题解没看懂所以才来写的这篇，也不算严谨证明。

首先遍历这颗树得到的序列是指这个，为了方便我就这么说了。

void dfs(int u)
{
    x[u] = cnt ++ ;
    for (int i = h[u]; ~i; i = ne[i])
        dfs(e[i]);
}

首先这颗树画成分层图，其每一层的 a 的值是一样的。

然后可以发现我们得到的序列必然满足性质二，而倒序遍历边会满足性质一和性质三，也就是相同的数先遍历后面的，这些画图都能看出来。

那它是否满足贪心呢？画图也能看出来。

因为我们建树是找前面满足条件的最靠后的一个数，所以每一层的数是把他们分了几块，互不相交。

比如第一层的 a_i = 1 的点其是就是把这个序列分成了好几块，而他们的子树就代表着它和后一个 a_i = 1 的点之间的区间，下面的几层也是把自己所在的块又分成了更小的几块，有点抽象，你可以把笛卡尔树那张图拿出来，然后把二叉树改成不知道几叉树（每个结点的儿子数不一定一样），差不多就那样。

所以我们倒序遍历边可以时使得越往后的数越小，且同时满足三个性质或者说限制。

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 100010;

int n;
int h[N], e[N], ne[N], idx;
int w[N], p[N], cnt;
int last[N], tr[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int lowbit(int x)
{
    return x & -x;
}

int query(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res = max(res, tr[i]);
    return res;
}

void update(int x, int v)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] = max(tr[i], v);
}

void dfs(int u)
{
    p[u] = cnt ++ ;
    for (int i = h[u]; ~i; i = ne[i])
        dfs(e[i]);
}

int main()
{
    scanf("%d", &n);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &w[i]), last[w[i]] = i;
        add(last[w[i] - 1], i);
    }

    dfs(0);

    LL res = 0;
    for (int i = n; i; i -- )
    {
        int t = query(p[i]) + 1;
        update(p[i], t), res += t;
    }

    cout << res << endl;

    return 0;
}