题解：CF2217E Definitely Larger

前言

掉大分。

但是这个星野真的很可爱吧（）

Solution(s)

考虑如何构造，可以粗略想到四种方向（~~水字数~~）。

从前往后

感觉就很没前途，如果我们要确定一个位置的值，需要让它前面的位置仍然合法，还需要后面的位置能够满足它自己的条件，约束太多，难以确定。

从后往前

虽然从后往前放好像也无法确定当前位置具体填什么值，但是我们在已知后缀的值排名的情况下，可以确定当前位置的值在其中的排名，然后可以进行插入，维护合法后缀并递推求解。

具体的，从后往前处理，对于位置，枚举其在后缀中的排名，若后缀中值更大且排名更高的元素数量恰好为，则插入当前元素，无合法位置则无解。

核心代码

vector<int> v;
for (int i = n; i >= 1; i--)
{
    int now = 0;
    auto pos = v.end();
    while (now < d[i] && pos != v.begin())
    {
        pos--;
        now += (p[*pos] > p[i]);
    }
    if (now < d[i])
        return void(puts("-1"));
    v.insert(pos, i);
}
for (int i = 1; i <= n; i++)
{
    ans[v[i - 1]] = i;
}

从小到大

对于排列，有一个常见 Trick，就是从值域角度考虑。

定义，假设当前要填，就一定会填到一个的位置。

因为以后填的值都比大，所以后面更大的位置全都能支配，其被支配次数恰为，因此需要。

填上过后，我们发现这个对左侧位置的贡献失效，即对于，

而后面的位置显然是没有受到丝毫影响，所以我们就可以开心地用相似的条件去填了。

如果发现没有位置可以填，说明无解。

还有一个事实，由于中元素的值单调不增，所以若存在就无解。

但是等等，同一时间可能有多个的位置，我们该填到哪呢？

给出结论：填到最前面的合法位置。

感性理解：

假如填到更后面的合法位置，可能使前面本来合法的位置变得不合法。
但是选前面的合法位置不仅不会影响后面的合法位置的合法性，还可能使更前面的不合法位置变得合法（由于上述事实保证，所以前面的不合法位置都可能变合法）。

所以应当选最前面的合法位置。

核心代码

for (int i = 1; i <= n; i++)
{
    g[i] = 0;
    for (int j = i + 1; j <= n; j++)
    {
        g[i] += (p[j] > p[i]);
    }
}
for (int v = 1; v <= n; v++)
{
    bool flag = 0;
    for (int i = 1; i <= n; i++)
    {
        if (p[i] == -1)
            continue;
        if (g[i] < d[i])
            return void(puts("-1"));
        if (g[i] == d[i])
        {
            ans[i] = v;
            for (int j = 1; j <= i - 1; j++)
                g[j] -= (p[i] > p[j]);
            p[i] = -1;
            flag = 1;
            break;
        }
    }
    if (!flag)
        return void(puts("-1"));
}

从大到小

相似地，我们考虑从大到小填值，发现我们会把填到的位置。

此时，对于前面的位置，已经满足了两个偏序条件，若再满足有关的偏序条件，就将支配它，即对于，，而后面的位置没有受到影响。

这样我们就算上了的影响，可以在以后忽略它，然后就可以继续用相同逻辑填接下来的了。

同理，优先选最左侧的位置，无合法位置则无解。

核心代码

for (int v = n; v >= 1; v--)
{
    bool flag = 0;
    for (int i = 1; i <= n; i++)
    {
        if (p[i] == -1)
            continue;
        if (d[i] == 0)
        {
            ans[i] = v;
            for (int j = 1; j <= i - 1; j++)
                d[j] -= (p[i] > p[j]);
            p[i] = -1;
            flag = 1;
            break;
        }
    }
    if (!flag)
        return void(puts("-1"));
}

时间复杂度

上述三种正确解法的时间复杂度都是。

总结

发现对于上面三种正确解法，都有一个共同点，她们都通过一些方式完全锁定当前决策的所有约束条件，并做出使某个位置一定可以合法的决策。

不知道这算不算很多（尤其是有关排列的）构造题的共通之处？