查看源代码：
CF2144.md

---
title: CF2144
createTime: 2025/9/17
categories:
    - IT
tags:
    - OI
---

## A

:::note 题意
给定一个数组，问能否分割成 $3$ 个非空段，使得每个非空段和 $\bmod 3$ 的值全部相同或全部不同。
:::

:::details code
```cpp
#include <bits/stdc++.h>
using namespace std;

inline bool check(int a, int b, int c) {
    return a==b&&b==c || a!=b&&b!=c&&c!=a;
}

const int maxn=64;
int s[maxn];

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i=1; i<=n; i++) {
            int a;
            cin >> a;
            s[i] = s[i-1] + a;
        }
        
        for (int l=1; l<=n; l++) {
            for (int r=l+1; r<n; r++) {
                if (check(s[l]%3, (s[r]-s[l])%3, (s[n]-s[r])%3)) {
                    cout << l << ' ' << r << '\n';
                    goto end;
                }
            }
        }
        
        cout << "0 0\n";
        
        end:;
    }
    
    return 0;
}
```
:::

## B

:::note 题意
有一个排列，部分位置缺失。你要填入缺失的数字，使其成为一个完整排列。  
定义排列的代价为：使得整个排列有序，所需排序的最短连续子串的长度。  
在所有可能的填法中，最大化这个代价。
:::

设 $l$ 为已经归位的前缀长度，$r$ 为已经归位的后缀长度，显然代价为 $\max\{n-l-r,0\}$（$\max$ 是为了解决 $l=r=n$ 的情况）

除了只有一个空位，已经能够确定的情况需要特判，总是有一种填空方法能够使一头一尾两个空不归位，此时代价最大。

:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=2e5+10;
int p[maxn];
int cnt[maxn];

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        for (int i=0; i<=n; i++) {
            cnt[i] = 0;
        }
        
        for (int i=1; i<=n; i++) {
            cin >> p[i];
            cnt[p[i]]++;
        }
        
        int l=0, r=0;
        
        for (int i=1; i<=n; i++) {
            if (p[i]==i || cnt[0]==1&&p[i]==0&&cnt[i]==0) {
                l++;
            } else {
                break;
            }
        }
        
        for (int i=n; i>=1; i--) {
            if (p[i]==i || cnt[0]==1&&p[i]==0&&cnt[i]==0) {
                r++;
            } else {
                break;
            }
        }
        
        cout << max(n-l-r, 0) << '\n';
    }
    
    return 0;
}
```
:::

## C

:::note 题意
给定两个序列 $a, b$，你可以任意交换 $a_i, b_i$（可以不交换），求使得 $a, b$ 不严格单调递增的方法数。
:::

依题意 DP，设 $f(i,0/1)$ 是 $1 \sim i$ 中最后一个不交换/交换的方法数。

设 $S_0(i) = a_{i-1} \le a_i \land b_{i-1} \le b_i$，  
$\quad S_1(i) = a_{i-1} \le b_i \land b_{i-1} \le a_i$

可得转移方程

$$
f(i,j) = S_{[j=1]}(i) f(i,0) + S_{[j=0]}(i) f(i,1)
$$

:::details
```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=128, mod=998244353;
int a[maxn][2];
int f[maxn][2];

int main () {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        
        for (int i=1; i<=n; i++) {
            f[i][0] = f[i][1] = 0;
        }
        
        for (int i=1; i<=n; i++) {
            cin >> a[i][0];
        }
        for (int i=1; i<=n; i++) {
            cin >> a[i][1];
        }
        
        f[0][0] = 1;
        for (int i=1; i<=n; i++) {
            for (int j=0; j<=1; j++) {
                for (int k=0; k<=1; k++) {
                    if (a[i-1][j]<=a[i][k] && a[i-1][!j]<=a[i][k]) {
                        f[i][k] += f[i-1][j];
                        f[i][k] %= mod;
                    }
                }
            }
        }
        
        cout << (f[n][0] + f[n][1]) % mod << '\n';
    }
    
    return 0;
}
```
:::

## D

:::note 题意

你的店铺现在要促销。具体而言，你要选择一个整数 $x > 1$，把价格 $c_i$ 变为 $\lceil c_i / x \rceil$。

接下来，你需要为商品贴上新的价格标签。旧的价格标签可以复用，打印一个新的价格标签需要花费 $y$。

求最大的利润。

:::

长见识了，原来整除分块还能这么出。

不难发现价格和标签成本二者的联动特别难求，所以枚举 $x \le \max\{2, \max c\}$ 是必然的。

用目标反过来表示原值，价格可以表示为

$$
\newcommand{\mset}[2]{\left\{ \kern{-0.3em} \begin{array}{c|c}
    #1 & #2
\end{array} \kern{-0.3em} \right\}}
\newcommand{\dmset}[2]{\mset{\displaystyle #1}{\displaystyle #2}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}

\begin{align*}
\sum_{i=1}^{n} \ceil{\frac{c_i}{x}}
    &= \sum_{v=1}^{\max \ceil{c_i/x}} v\ \# \dmset{i}{ \ceil{\frac{c_i}{x}} = v } \\
    &= \sum_{v=1}^{\max \ceil{c_i/x}} v\ \# \dmset{i}{x(v-1) < c_i \le vx}
\end{align*}
$$

而重复标签数量可以如下计算：

$$
\newcommand{\mset}[2]{\left\{ \kern{-0.3em} \begin{array}{c|c}
    #1 & #2
\end{array} \kern{-0.3em} \right\}}
\newcommand{\dmset}[2]{\mset{\displaystyle #1}{\displaystyle #2}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}

\begin{align*}
&\sum_{v=1}^{\max \ceil{c_i/x}} \max\left\{ 0, \#\dmset{i}{\ceil{\frac{c_i}{x}} = v} - \#\dmset{i}{c_i=v} \right\} \\
=& \sum_{v=1}^{\max \ceil{c_i/x}} \max\left\{ 0, \#\dmset{i}{x(v-1) < c_i \le vx} - \#\dmset{i}{c_i=v} \right\}
\end{align*}
$$

复杂度看上去很大，但实际上是一个调和级数的形式

$$T = \sum_{x=1}^{\max c} \frac{\max c}{x} = O(m \log m), \quad m = \max c$$

:::details Code
```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int maxn=2e5+10, inf=0x3f3f3f3f3f3f3f3f;
int c[maxn];
int cnt[2*maxn];
int prec[2*maxn];

inline int ceildiv(int a, int b) {
    return (a + b - 1) / b;
}

signed main () {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    while (t--) {
        memset(cnt, 0, sizeof(cnt));
        
        int n, y;
        cin >> n >> y;
        
        int maxc=0;
        for (int i=1; i<=n; i++) {
            cin >> c[i];
            cnt[c[i]]++;
            maxc = max(maxc, c[i]);
        }
        
        for (int i=1; i<=2*maxc; i++) {
            prec[i] = prec[i-1] + cnt[i];
//          if (cnt[i]) printf("prec[%d]=%d\n", i, prec[i]);
        }
        
        int ans = -inf;
        for (int x=2; x<=max(2ll, maxc); x++) {
//          printf("at x=%d:\n", x);
            
            int p=0;
            for (int v=1; v<=ceildiv(maxc, x); v++) {
                int count = prec[v*x] - prec[x*(v-1)];
//              if (count) printf("\t%d in (%d,%d] turn to %d (%d - %d)\n", count, x*(v-1), v*x, v, prec[v*x], prec[x*(v-1)]);
                p += v * count;
                p -= y * max(0ll, count - cnt[v]);
            }
            
//          printf("tot: %d\n", p);
            ans = max(ans, p);
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}
```
:::

## E

:::note 题意

给定一个序列 $h_i$，设它的前缀/后缀最大值集合分别为 $L, R$，求使得 $L, R$ 不变的子序列的数量 $\bmod 998244353$。

:::

把解拆成两部分：以 $i$ 结尾，包含前 $j$ 个前缀最大值的方案数 $f(i,j)$；以 $i$ 开头，包含前 $j$ 个后缀最大值的方案数 $g(i,j)$。

接下来看看怎么求 $f(i, j)$（$g$ 是对称的）。

$f(i, j)$ 可以有三种来源：

1. 不选，无要求，有 $f(i-1,j)$ 转移；
2. 选且不影响 $j$，要求 $h_i \le L_j$，从 $f(i-1, j)$ 转移；
3. 选且影响 $j$，要求 $h_i = L_j$，从 $f(i-1, j)$ 转移。

于是

$$
f(i, j) = \begin{cases}
    f(i-1, j), &\quad h_i > L_j \\
    2f(i-1, j) + f(i-1, j-1), &\quad h_i = L_j\\
    2f(i-1, j), &\quad h_i < L_j
\end{cases}
$$

使用支持区间乘、单点加和单点查询的线段树维护 DP 值。

怎么把 $f, g$ 拼接在一起呢？

为了保证唯一性，枚举子序列中第一个最大值 $h_i=\max h$ ，则不难证明

$$\mathrm{ans} = \sum_{h_i = \max h} f(i-1, |L|-1)\ (g(i+1, |R|) + g(i+1, |R|-1))$$

总时间复杂度 $O(n \log n)$。

:::details Code (Easy Version)

感觉 Easy Version 是给懒得打线段树的人设计的。

```cpp
#include <bits/stdc++.h>
using namespace std;

const int maxn=5100, mod=998244353;

int lcnt, rcnt;
int l[maxn], r[maxn];
int h[maxn], f[maxn], g[maxn];
int ff[maxn], gg[maxn];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        int maxh = 0;
        for (int i=1; i<=n; i++) {
            cin >> h[i];
            maxh = max(maxh, h[i]);
            f[i] = g[i] = 0;
        }
        
        lcnt = rcnt = 0;
        for (int i=1; i<=n; i++) {
            if (h[i] > l[lcnt]) {
                l[++lcnt] = h[i];
            }
        }
        for (int i=n; i>=1; i--) {
            if (h[i] > r[rcnt]) {
                r[++rcnt] = h[i];
            }
        }
        
        f[0] = 1;
        ff[0] = f[lcnt-1];
        for (int i=1; i<=n; i++) {
            for (int j=lcnt; l[j]>=h[i]; j--) {
                f[j] = (f[j] << 1) % mod;
                if (l[j] == h[i]) {
                    f[j] = (f[j] + f[j-1]) % mod;
                }
            }
            ff[i] = f[lcnt-1];
        }
        
        g[0] = 1;
        for (int i=n; i>=1; i--) {
            gg[i] = (g[rcnt] + g[rcnt-1]) % mod;
            
            for (int j=rcnt; r[j]>=h[i]; j--) {
                g[j] = (g[j] << 1) % mod;
                if (r[j] == h[i]) {
                    g[j] = (g[j] + g[j-1]) % mod;
                }
            }
        }
        
        int ans=0;
        for (int i=1; i<=n; i++) {
            if (h[i] == maxh) {
                ans += ff[i-1] * (long long)gg[i] % mod;
                ans %= mod;
            }
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}
```

:::

:::details Code (Hard Version)
```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int maxn=3e5+10, mod=998244353;

int h[maxn];
int ff[maxn], gg[maxn];
int lcnt, rcnt;
int l[maxn], r[maxn];

struct segtree {
    int a[maxn * 4], lz[maxn * 4];
    
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return (x << 1) | 1; }
    inline int md(int x, int y) { return (x + y) >> 1; }
    
    inline void clear() {
        a[1] = lz[1] = 0;
    }
    
    inline void pushdown(int tn) {
        int lcn = lc(tn), rcn = rc(tn);
        a[lcn] = a[lcn] * lz[tn] % mod;
        a[rcn] = a[rcn] * lz[tn] % mod;
        lz[lcn] = lz[lcn] * lz[tn] % mod;
        lz[rcn] = lz[rcn] * lz[tn] % mod;
        lz[tn] = 1;
    }
    
    inline int query(int tn, int tl, int tr, int x) {
        if (tl == tr) {
            return a[tn];
        }
        
        pushdown(tn);
        
        int mid = md(tl, tr);
        if (x <= mid) {
            return query(lc(tn), tl, mid, x);
        } else {
            return query(rc(tn), mid+1, tr, x);
        }
    }
    
    inline void add(int tn, int tl, int tr, int x, int y) {
        if (tl == tr) {
            a[tn] += y;
            a[tn] %= mod;
            return;
        }
        
        pushdown(tn);
        
        int mid = md(tl, tr);
        if (x <= mid) {
            add(lc(tn), tl, mid, x, y);
        } else {
            add(rc(tn), mid+1, tr, x, y);
        }
    }
    
    inline void mul2(int tn, int tl, int tr, int x, int y) {
        if (tr < x || y < tl) {
            return;
        }
        
        if (x <= tl && tr <= y) {
            a[tn] = (a[tn] << 1) % mod;
            lz[tn] = (lz[tn] << 1) % mod;
            return;
        }
        
        pushdown(tn);
        
        int mid = md(tl, tr);
        mul2(lc(tn), tl, mid, x, y);
        mul2(rc(tn), mid+1, tr, x, y);
    }
} f, g;

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int t;
    cin >> t;
    
    while (t--) {
        f.clear();
        g.clear();
        
        int n;
        cin >> n;
        
        int maxh = 0;
        for (int i=1; i<=n; i++) {
            cin >> h[i];
            maxh = max(maxh, h[i]);
        }
        
        lcnt = rcnt = 0;
        for (int i=1; i<=n; i++) {
            if (h[i] > l[lcnt]) {
                l[++lcnt] = h[i];
            }
        }
        for (int i=n; i>=1; i--) {
            if (h[i] > r[rcnt]) {
                r[++rcnt] = h[i];
            }
        }
        
        f.add(1, 0, lcnt, 0, 1);
        for (int i=1; i<=n; i++) {
            ff[i-1] = f.query(1, 0, lcnt, lcnt - 1);
            
            int j0 = lower_bound(l+1, l+lcnt+1, h[i]) - l;
//          printf("j0: %lld\n", j0);
            
            int add = f.query(1, 0, lcnt, j0-1);
            f.mul2(1, 0, lcnt, j0, lcnt);
            if (l[j0] == h[i]) {
                f.add(1, 0, lcnt, j0, add);
            }
            
//          for (int j=0; j<=lcnt; j++) {
//              printf("f(%lld, %lld) = %lld\n", i, j, f.query(1, 0, lcnt, j));
//          }
        }
        
        g.add(1, 0, rcnt, 0, 1);
        for (int i=n; i>=1; i--) {
            gg[i] = (g.query(1, 0, rcnt, rcnt) + g.query(1, 0, rcnt, rcnt-1)) % mod;
            
            int j0 = lower_bound(r+1, r+rcnt+1, h[i]) - r;
//          printf("j0: %lld\n", j0);
            
            int add = g.query(1, 0, rcnt, j0-1);
            g.mul2(1, 0, rcnt, j0, rcnt);
            if (r[j0] == h[i]) {
                g.add(1, 0, rcnt, j0, add);
            }
            
//          for (int j=0; j<=rcnt; j++) {
//              printf("g(%lld, %lld) = %lld\n", i, j, g.query(1, 0, rcnt, j));
//          }
        }
        
        int ans=0;
        for (int i=1; i<=n; i++) {
            if (h[i] == maxh) {
                ans += ff[i-1] * gg[i] % mod;
                ans %= mod;
            }
        }
        
        cout << ans << '\n';
    }
    
    return 0;
}
```
:::