3 | The 2nd Universal Cup. Stage Ω: Atlantis (Prime Contest)

cmll02 · 2024-06-13 18:12:04 · 闲话

The 2nd Universal Cup. Stage Ω: Atlantis (Prime Contest)

Prime Contest 也是 Prime。

3

Balanced Permutations

题意

给定一个大小为 n 的排列 p，如果排列的一个（连续）子数组的最大值是其第一个或最后一个元素，则该子数组被认为是“不稳定的”。如果一个排列中“不稳定”子数组的数量在所有大小为 n 的排列中是最少的，则这个排列被认为是“平衡的”。

给定整数 n、l 和 k，报告字典序第 l 小的“平衡”排列和字典序第 k 大的“平衡”排列。如果不存在这样的排列，则输出 -1。

题解

这个题极其恶心。

可以看到平衡度就是笛卡尔树的子树大小和。

l=1 的做法

打个表，发现每次合法的最大值的位置在一个区间内，瞪出规律之后，把最大值尽量往前放，然后递归构造。往前放是为了让左半边的最大值变小，从而得到更小的字典序。

l>1 的做法

容易发现我们不会在 l=1 的做法做出很大的调整，于是我们只要从最右边的叶子结点一直往上找一个祖先 u，使得 u 子树有 \ge l 种排列方案，重排即可。

至于求重排方案，没法直接对笛卡尔树 dp，因为你无法辨别选择最大值的方案如何影响字典序大小。但是你可以从前到后枚举每个位置填多少，然后算出字典序比当前小的合法方案数。这样就可以 dp 了。

k 的做法

和上面差不多。

下面是一份来自 OnO 的 l=1 代码。

namespace OnO {
    int hgh[100005];
    inline void init(void) { for(int i=3; i<=100000; ++i) hgh[i]=hgh[(i-1)/2]+1; }
    inline int* consMin(int*A,int n,int&val) {
        if(n==0) return A;
        if(n==1) {
            *A=(++val);
            return A+1;
        }
        int cnt=n-(1<<(hgh[n]+1))+1;
        int siz=1<<hgh[n];
        int L=0,R=0;
        if(cnt) ++L,--cnt;
        R=min(cnt,siz);
        cnt-=R;
        L+=cnt;
        A=consMin(A,siz-1+L,val);
        int*B=consMin(A+1,siz-1+R,val);
        *A=(++val);
        return B;
    }
    inline void consMin(int*A,int n) {
        int v=0;
        consMin(A,n,v);
    }
    inline int* consMax(int*A,int n,int&val) {
        if(n==0) return A;
        if(n==1) {
            *A=(++val);
            return A+1;
        }
        int cnt=n-(1<<(hgh[n]+1))+1;
        int siz=1<<hgh[n];
        int R=min(cnt,siz);
        int L=cnt-R;
        L+=siz-1; R+=siz-1;
        int*B=consMax(A+L+1,R,val);
        A=consMax(A,L,val);
        *A=(++val);
        return B;
    }
    inline void consMax(int*A,int n) {
        int v=0;
        consMax(A,n,v);
    }
}