自动搬运

查看原文

来自洛谷，原作者为

	XFlypig Stay here forever

搬运于2025-08-24 21:55:05，当前版本为作者最后更新于2024-07-15 16:51:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3971 [TJOI2014] Alice and Bob

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

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

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

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

• 性质一：$a$ 相同的数，肯定是单调递减的。

• 性质二：对于每个数 $x_i$，他前面必有一个 $j$ 满足 $a_j = a_i - 1$ 且 $x_j < x_i$。

• 性质三：对于任意一个 $j$ 满足 $j < i$ 且 $a_j \ge a_i$，必须满足 $x_j > x_i$。

由性质一和性质二可得 $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;
}