题解：P11987 [JOIST 2025] 集邮比赛 4 / Collecting Stamps 4

· · 题解

传送门

闲话：这道题被拿来作考试 T3，我成功证明出重要结论并打出 O(n^2) 做法，然而爆零，原因是预处理边界问题和极大值不够大。场下思考了很久的优化，最终在同机房大佬的一些提示下做出来啦！

题意

有一个节点数为 2n 的环，顺时针遍历节点依次编号为 1 \sim 2n，给定每个点的颜色 a_{1 \sim 2n}，保证环上共有 n 种颜色且每种颜色只出现 2 次。你可以选择一个节点 i，花费 c_i，接下来可以交换相邻两个节点的颜色（但不能交换 i 和 i - 1，如果 i 为 1 则不能交换 1 和 2n），每次交换花费 x。你携带了足够的集章卡，每张卡上有两个空格，完成上述所有操作后，从 i 出发顺时针依次遍历 2n 个节点，每到一个节点可以选择用该节点的颜色给若干张卡盖上印章，但每张卡必须先在左空格盖章，再在右空格盖章。接下来 q 个询问，每个询问给定一个整数 k，你需要回答如果想收集至少 k 种不同的集章卡，需要的最少花费。

设 (x,y) 表示当前集章卡左边颜色为 x，右边颜色为 y，两张集章卡 (x_1,y_1),(x_2,y_2) 不同当且仅当 x_1 \ne x_2 或 y_1 \ne y_2。

思路

假设我们已经确定了起始点 i 并完成了交换操作，将 i 及 i 以后 2n - 1 个节点的颜色表示为 a_{1 \sim 2n}，设 l_{j},r_{j} 表示颜色为 j 的两个位置且满足 l_{j} < r_{j}（l_{j},r_{j} 是相对起始点 i 的位置，例如：当 i = 3，l_j 原本的位置为 5，这里要将 l_{j} 变为 5 - 3 + 1 = 3）。由于盖章时只能先盖左空格再盖右空格，如果存在一种盖章的方式使得可以收集到集章卡 (a,b) 当且仅当 l_a < r_b（否则 a 第一次出现的位置在 b 第二次出现以后，无法做到先盖 a 再盖 b）。

有一个重要的结论：如果按顺序依次遍历 a_{1 \sim 2n} 后得到的集章卡种类不为 n^2 种（种数最多为 n^2），一定存在一种方式使得交换一次后重新遍历 a_{1 \sim 2n} 得到的集章卡种类数加一。

考虑证明：首先，一次交换最多改变两种颜色的位置关系（例如 \dots x,y \dots 变为 \dots y,x \dots），因此一次交换最多会使重新遍历得到的集章卡种类加一（即原本可能是 l_{y} > r_{x}，进行一次交换后 l_{y} < r_{x}，其它颜色位置关系不变）。由于种类数没有顶到上界，因此一定存在一对 x,y 使得 l_{y} > r_{x}，即在 a 中的位置关系为 \dots x \dots x \dots y \dots y \dots。

设 y 第一次出现的位置的左边为 z，我们对它进行分类讨论：

由于一定存在 \dots x \dots x \dots y \dots y \dots，那么我们可一定以通过上述方式不断将 y 向 x 靠近，直到 x,y 相邻（或在 y 改变的过程中找到第一种情况的 z），该结论得证。

此时 O(n^2) 做法就很简单了。

考虑以每个位置为起点，不妨设该点为 i，统计不进行任何操作时从 i 开始顺时针遍历每个点一次可以收集到的不同集章卡方案数。具体统计方式是：钦定某个颜色 j 作为集章卡左空格的颜色，统计 l_{j} \sim n 里不同颜色数目（由于 r_{j} > l_{j}，在 l_{j} 时盖左空印章一定不小于在 r_{j} 时盖左空格印章所得的最终方案数），依次加入总方案数。由于每次统计左空格颜色不同，且尽量增大了以 j 为左空格颜色的方案数，可以做到不重不漏，可以通过修改后缀和的方式实现单次统计 O(n)，n 次总 O(n^2)。

对于查询，先把查询离线下来并按 k 值排序；并把上一段以每个位置为起点的情况按可收集到的方案数为第一关键字，花费 c_{i} 为第二关键字排序。由于要使集章卡情况数加一都要花费 x，因此当两种方案的集章卡情况数相同时，选择花费小的那种一定更好，于是可以从前往后依次回答，回答的过程中跳排序后以某个位置为起点的信息即可做到 O(n + q)，对于方案数比查询大且花费更小的情况可以用后缀最小值解决，实现细节见代码，查询部分复杂度为 O(n \log n + q \log q)。

考虑优化统计不进行任何操作时从 i 开始顺时针遍历每个点一次可以收集到的不同集章卡方案数的复杂度。显然如果任取两种颜色方案数为 n^2，那么我们考虑用总方案数减去不可构成的情况数即为所求。考虑到只有 l_{x} < r_{y} 的时不能构成形如 (x,y) 的集章卡（l_{i},r_{i} 含义见第一段），我们对 l_{1 \sim n} 排序（这里只是方便推式子，代码里并不需要），由于 l_{j} 是相对位置，在它之前有 l_{j} - 1 个位置是其它颜色的 l 或 r，又有 j - 1 个其它颜色的 l 在前面出现过。

欸？发现什么没有，(l_{j} - 1) - (j - 1) = l_{j} - j 的意义就是 l_{j} 之前不为 l 的数量（即 l_{j} 之前 r 的数量）！对于当前起始点，我们要的集章卡方案数就是 n^2 - \sum_{i = 1}^{n} (l_{i} - i) = n^2 + \sum_{i = 1}^{n} i - \sum_{i = 1}^{n} l_{i} = n^2 + \frac{n \times (n+1)}{2} - \sum_{i = 1}^{n} l_{i}。明显这个式子是不基于 l_{1 \sim n} 递增这个性质的，又因为 n^2 + \frac{n \times (n+1)}{2} 恒定不变，只需求出 \sum_{i = 1}^{n} l_{i}。初始时求出 sum = \sum_{i = 1}^{n} l_{i}，每移动一个位置所有 l 的相对位置减一（即总和 sum 减 n），又因为当前起始位置的前一个位置的 l 会变化，在 sum 里加上新的 l 即可，实现细节见代码，该部分复杂度为 O(n)。

总复杂度 O(n \log n + q \log q)，瓶颈在排序。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,q,sum=0,a[2000005],c[1000005],l[1000005],r[1000005],minn[1000005],ans[1000005];
struct node
{
    int us,cs;
}p[1000005];
struct nide
{
    int c,id;
}ask[500005];
bool cmp1(node x,node y)
{
    return x.cs<y.cs;
}
bool cmp2(nide x,nide y)
{
    return x.c<y.c;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=2*n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=2*n;i++)
    {
        cin>>c[i];
    }
    for(int i=2*n;i>=1;i--)
    {
        if(r[a[i]]==0)
        {
            r[a[i]]=i;
            continue;
        }
        l[a[i]]=i;
        sum+=l[a[i]];
    }
    for(int i=1;i<=2*n;i++)
    {
        if(i!=1)
        {
            sum-=l[a[i-1]];
            swap(l[a[i-1]],r[a[i-1]]);
            r[a[i-1]]+=2*n;
            sum+=l[a[i-1]];
            sum-=n;
        }
        p[i].cs=n*n+n*(n+1)/2-sum;
        p[i].us=c[i];
    }
    sort(p+1,p+2*n+1,cmp1);
    p[0].cs=0;
    p[0].us=5e18;
    minn[2*n+1]=5e18;
    for(int i=2*n;i>=0;i--)
    {
        minn[i]=min(minn[i+1],p[i].us);
    }
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        cin>>ask[i].c;
        ask[i].id=i;
    }
    sort(ask+1,ask+q+1,cmp2);
    int nu=5e18,nc=0,nh=0;
    for(int i=1;i<=q;i++)
    {
        int c=ask[i].c,id=ask[i].id;
        while(nh<2*n&&p[nh+1].cs<=c)
        {
            nh++;
            nu=nu+(p[nh].cs-nc)*x;
            nu=min(nu,p[nh].us);
            nc=p[nh].cs;
        }
        ans[id]=min(nu+(c-nc)*x,minn[nh+1]);
    }
    for(int i=1;i<=q;i++)
    {
        cout<<ans[i]<<'\n';
    }
    return 0;
}