题解：CF773E Blog Post Rating

tallnut · 2025-12-18 22:51:15 · 题解

前几天某同学翻到此题的一个神秘的最短解，码长非常短，且时间复杂度线性。研究了一会研究明白了，然后发现洛谷题解区居然没有这个做法，遂来写题解。

Part 1. 并查集去重

第一步和之前的题解一样：a 单调不降一定是最优的，Exchange Argument 即可证明。

使用并查集将每个输入的 x 改为：\le x 的、没出现过的最大整数。易知处理完之后的 x 两两不同。同时记录每个数是否出现过。

具体地，令并查集 \mathrm{fa}_i 表示 \le i 的没出现过的最大整数，每次直接令 x\gets\mathrm{fa}_x，给 x 打上标记，然后维护并查集：\mathrm{fa}_x\gets\mathrm{fa}_{x-1}。

因为重复的 a_i 是冗余信息，而这样做可以在保持相对大小关系的同时“摊平”等号关系，并不会影响正确性。

可是，即使是带上路径压缩加上启发式合并的并查集也是 \Theta(n\alpha(n)) 啊，虽然 \alpha(n) 很小但它也在那啊，你凭什么说这是线性？

事实上，利用此题并查集的特殊结构，只需要普通路径压缩即可做到严格线性。用均摊分析思想，因为每一次这样的操作都会消灭一整条链（由于路径压缩），则每条边 u\rightarrow u-1 被经过的次数都是常数次。设值域为 V，则此处复杂度 \Theta(n+V)。

Part 2. 考虑评分变化图象

所有 x 两两不同是非常重要的性质。再结合将所有 a_i 从小到大排序加入的结论，最优解图象必形如：

• 从 0 开始；
• 先有一个下降段（每次严格 -1）；
• 再一个不变段（该段长度 \le1，否则就必有重复的数，与 x 两两不同矛盾）；
• 最后一个上升段（每次严格 +1，这是由两两不同的性质保证的，不会出现其他做法中 +1 和不变交替的情况）；

注意这三个段中任意一个的长度都有可能为 0。

相当于只有两种图象，一个是 V 形，另一个是 V 形的两侧之间加一条平着的线。

有了这个性质，图象就很好刻画了。我们令 p 为下降段长度的相反数（也就是图象最低点，注意 p 非正）；r 为下降段长度加上不变段长度。

不难发现 p,r 确定后整个图象就定死了，我们只需要实时维护 p,r 即可确定答案，为最低点加上上升段的长度，p+(i-r)=p+i-r。

易知任何时刻都有 r\ge-p（-p 即 p 的绝对值）。

Part 3. 分讨加入一个新数 x 对结构的影响

x>p

则此时 x 加入上升段，不用处理。而 p 在处理过程中单调不升，于是 x 永远不会需要考虑。于是这种情况不需要任何处理。

x=p

当前的数就是最小值，则这个数会加入不变段，r\gets r+1。

x<p

该数显然会加入下降或者不变段，所以先 r\gets r+1。

但是 x<p，这个 x 很想逼着 p 继续往下走，需要进一步考虑这可能造成什么连锁反应。只有两种可能的情况（因为在此之前 r\ge-p，r\gets r+1 之后就有 r+p\ge1 了）：

\small{r+p\ge2}

此时不变段长度 \ge 2，违反了之前“不变段长度不超过 1”的结论。于是我们只能进行修补：把整个图象往下凹一格，即不变段最左边一格的变成下降，最右边的一格变成上升。

不难发现这会导致下降段长度 +1，不变段长度 -2，因此 r\gets r-1,p\gets p-1。

\small{r+p=1}

则不变段长度为 1。

我们考虑这一个 x 能否逼最低点下降：

• 没出现过 p 这个数，则最低点还没被摁死，可以“局部微调”，继续下降，相当于将整个后面的结构平稳地下移一格，下降段 +1，不变段 -1，p\gets p-1；
• 否则，想再让一个数落在 p，就违反了高度唯一的性质。我们无法新增一次合法的 -1，就不能继续下降了，这里积累的压力只能等到以后“整体重构”，套用 r+p\ge2 的做法强行使之下降。

  Part 4. Code

  通过以上讨论，我们可以得到如下十分简洁的代码： :::success[AC Code] AC 记录。

#include <bits/stdc++.h>
#define rep1(i,x,y) for (int i = (x);i <= (y);i++)
using namespace std;
const int N = 2e6 + 10;
int n,p,r,x;
int f[N];
bool v[N];
int* fa = f + N / 2;
bool* vis = v + N / 2;
int find(int x)
{
    if (fa[x] == x)
        return x;
    return fa[x] = find(fa[x]);
}
signed main()
{
    rep1(i,-1e6,1e6)
        fa[i] = i;
    cin >> n;
    rep1(i,1,n)
    {
        cin >> x;
        x = find(x);
        vis[x] = true;
        fa[x] = fa[x - 1];
        if (x == p)
            r++;
        else if (x < p)
        {
            r++;
            if (p + r == 1)
            {
                if (!vis[p])
                    p--;
            }
            else
            {
                p--;
                r--;
            }
        }
        cout << p + i - r << '\n';
    }
}

:::