P4769 [NOI2018]冒泡排序

NOI2018D1T2

题目可以转化为：要求排列中不存在长度>=3的下降子序列。

因为如果出现的话，那么这个下降子序列中间的元素需要先与左边比它大的元素交换再与右边比它小的元素交换，需要折返一下，显然就不合法了。

这又等价于可以将序列划分为2个上升子序列。

这个怎么证明呢?好像显然啊....因为如果能分为三个那一定有>=3的下降子序列

然后假设前i个位置最大数是j,那么我们在后面放的时候,会发现大于j的数目是可以随便填的,而小于j的数只能从小到大挨个放,他们构成第二个上升子序列

$f[i][j]$ 表示我们还剩下i个数没有填,后j个数值是大于当前最大值的"非限制元素"答案

然后转移时枚举下一个位置填一个限制元素或某个非限制元素

如果放限制元素,非限制的数量不变,否则假设放入第k个非限制元素,非限制元素的数量要减少k个,因为最大值发生了变化,能够填的非限制元素减少k个

f[i][j]=\sum_{k=0}^j{f[i-1][j-k]}

注意我们第二维是还有多少个非限制哦

边界 $f[0][0]=1$

这好像是前缀和?qwq

f[i][j]=f[i][j-1]+f[i-1][j]

另外如果打个表或者直接看会发现这个是卡特兰数qaq

再考虑限制吧,假设当前做到第i位,给定的排列这一位是 $a_i$ ,后面有 $b_i$ 个数比他大,前面有 $c_i$ 比他小,然后现在非限制元素还有nw个

所以如果填入数字 $p_i$ > $a_i$

先把nw和 $b_i$ 取个min,因为填完之后非限制元素小于等于 $b_i$ 个

如果此时nw为0了,后面只能按顺序填入了qaq,这个字典序是严格不大于给定排列的,可以退出了

否则我们就要 $\sum_{k=0}^{nw-1}{f[n-i][k]}$ 这个就是前缀和为 $f[n-i+1][nw-1]$

然后再考虑 $p_i=a_i$ 是否合法呢?

如果 $b_i$ 更新了nw,说明 $a_i$ 本身就非限制啊

否则 $a_i$ 一定要是当前最小的,相当于填入了一个限制元素,也是合法的

否则就填入了一个不合法元素,一定会导致全局不合法,就不能

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 6e5 + 7;
const int  P = 998244353;
#define ll long long
ll fac[MAXN << 1], ifac[MAXN << 1];
int n, T, a[MAXN], mi[MAXN];

inline ll C(int n, int m) {
    return (m >= 0) ? (fac[n] * ifac[m] % P * ifac[n - m] % P) : 0;
}

inline ll ksm(ll x, ll y) {
    ll  ans = 1;
    while(y) {
        if(y & 1)ans = ans * x % P;
        x = x * x % P;
        y >>= 1;
    }
    return ans;
}

inline ll S(ll n, ll m) {
    if(m > n)return 0;
    return (C((n << 1) - m, n - m) - C((n << 1) - m, n - m - 1) + P ) % P;
}

struct Bit {
    int tr[MAXN];
#define lowbit(x) (x&(-x))
    inline void add(int x, int val) {
        for(; x <= n; x += lowbit(x))tr[x] += val;
    }
    inline int query(int x) {
        ll ret = 0;
        for(; x; x -= lowbit(x))ret += tr[x];
        return ret;
    }
    inline void clear() {
        for(int i = 1; i <= n; ++i)tr[i] = 0;
    }
} tree;

inline void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);
    for(int i = n; i >= 1; --i)tree.add(a[i], 1);
    mi[n] = a[n];
    for(int i = n - 1; i >= 1; --i)mi[i] = min(mi[i + 1], a[i]);
    int mx = 0;
    int cmx = 0;
    ll ans = 0;
    for(int i = 1; i <= n; ++i) {
        // printf("%d %d\n", mi[i], mx);
        if(cmx > mi[i])break;
        ans = (ans + S(n - i + 1, tree.query(max(mx, a[i])) + 1)) % P;
        if(a[i] < mx)cmx = max(cmx, a[i]);
        mx = max(mx, a[i]);
        tree.add(a[i], -1);
    }
    printf("%lld\n", ans);
}

inline void init() {
    fac[0] = 1;
    int up = (MAXN << 1) - 10;
    for(int i = 1; i <= up; ++i)fac[i] = fac[i - 1] * i % P;
    ifac[up] = ksm(fac[up], P - 2);
    for(int i = up - 1; i >= 2; --i) {
        ifac[i] = ifac[i + 1] * (i + 1) % P;
    }
    ifac[0] = ifac[1] = 1;
    // printf("%d %d\n", ifac[2], ifac[3]);
    // printf("%lld %lld %d\n", C(3, 2), C(5, 4), fac[5]*ifac[4] % P * ifac[1]);
}

int main() {
    init();
    scanf("%d", &T);
    for(int i = 1; i <= T; ++i)solve(), tree.clear();
    return 0;
}

qwq

夏晓光(loveJY)的博客

扫描线详解