链接：https://codeforces.com/contest/2137

A. Collatz Conjecture

    这题读假了以为是找出全部的可能值。

算法：

    模拟。

思路：

    无。

关键代码：

void solve()
{
    ll k, x;
    cin >> k >> x;

    cout << (x << k) << endl;
}

B. Fun Permutation

算法：

    构造，数学。

思路：

    玩几组样例可以发现规律在 \(n\) 的值上，将 \( n \)转换为三进制，其结果只有 \(0,1,2\) 三种情况：

• 当值为 \(0\) 或 \(1\) 时，两两之间全部构造成 \(3\) 的倍数即可。
• 当值为 \(2\) 时，两两之间全部构造成 \(4\) 的倍数即可。

关键代码：

void solve()
{
    int n;
    cin >> n;
    vector<int> p(n + 1);
    for (int i = 1; i <= n; ++i)
        cin >> p[i];

    if (n % 3 == 0 || (n + 1) % 3 == 0)
    {
        for (int i = 1; i <= n; ++i)
        {
            if (p[i] % 3 == 0)
                cout << p[i] << ' ';
            else
            {
                if ((p[i] + 1) % 3 == 0)
                    cout << p[i] - 1 << ' ';
                else
                    cout << p[i] + 1 << ' ';
            }
        }
    }
    else
    {
        for (int i = 1; i <= n; ++i)
            cout << n + 1 - p[i] << ' ';
    }

    cout << endl;
}

C. Maximum Even Sum

算法：

    打表，找规律。

思路：

    直接打表即可。

关键代码：

void solve()
{
    ll a, b;
    cin >> a >> b;

    if (((a & 1) && (b - 2) % 4 == 0) || (a % 2 == 0 && (b & 1)))
    {
        cout << -1 << endl;
        return;
    }

    if ((a & 1) && (b & 1))
        cout << a * b + 1 << endl;
    else
        cout << a * (b / 2) + 2 << endl;
}

D. Replace with Occurrences

算法：

    构造。

思路：

    \(b\) 中相同的值构造成一样的元素，注意一下大小即可。

关键代码：

void solve()
{
    ll n;
    cin >> n;
    vector<ll> b(n);
    for (auto &x : b)
        cin >> x;

    map<int, vector<int>> m;
    for (int i = 0; i < n; ++i)
        m[b[i]].push_back(i);

    vector<int> ans(n);
    ll val = 1;
    for (auto [num, v] : m)
    {
        ll cnt = v.size();

        if (cnt % num)
        {
            cout << -1 << endl;
            return;
        }

        for (auto x : v)
        {
            ans[x] = val;
            --cnt;

            if (cnt % num == 0)
                ++val;
        }
    }

    for (auto x : ans)
        cout << x << ' ';
    cout << endl;
}

E. Mexification

算法：

    模拟，数学。

思路：

    通过打表可以发现，操作存在周期性，且周期性都为 \(2\)，但是有一些特殊的数组其周期性是在 \(3\) 才开始展现，既第 \(1\) 次操作和第 \(3\) 次操作得到的数组是不一样的，如：\(0 1 1 2 3\)。

    所以不能无脑奇数执行一次操作，偶数执行两次操作，需要做出特判，这里直接选择在 \(k\) 大于 \(1\) 且为奇数时执行三次，\(k\) 为 \(1\) 时还是执行 \(1\) 次， 所以总的时间复杂度为 \(O(n)\)。

    对于每次操作中每个元素的更新：

• 先对整个数组统计每个元素出现的次数，然后求出全体 \(mex\)。
• 对于每个元素，如果其只出现了一次，其可能对答案造成影响，既：
  • 如果 \(a[i] < mex\)，那么对于其他所有元素的 \(mex\) 会在 \(a[i]\) 处断开，此时 \(a[i] = a[i]\)。
  • 如果 \(a[i] > mex\)，那么不会对答案照成影响，\(a[i] = mex\)。
• 如果出现了多次，其值就为 \(mex\)。

关键代码：

void solve()
{
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (auto &x : a)
        cin >> x;

    if (k > 1)
        k = k % 2 + 2;

    for (int tt = 0; tt < k; ++tt)
    {
        vector<ll> cnt(n + 1, 0);
        for (int i = 0; i < n; ++i)
            ++cnt[a[i]];

        ll mex = 0;
        while (cnt[mex])
            ++mex;

        for (int i = 0; i < n; ++i)
        {
            if (cnt[a[i]] == 1)
                a[i] = min(mex, a[i]);
            else
                a[i] = a[i];
        }
    }

    cout << accumulate(all(a), 0ll) << endl;
}

F. Prefix Maximum Invariance

算法：

    贡献法，贪心，堆。

思路：

    题目要求计算一个全区间函数的总和，这类问题通常可以通过贡献法来解决。

     核心思路是：枚举每个位置 \(i\)，找出它在所有区间中的贡献，再累加起来。

情况一：当 \(a_i = b_i\)

    此时在任何包含 \(i\) 的区间中，都可以令 \(z_i = a_i = b_i\)，不需要额外条件。

    它的贡献就是所有区间数目：

• 左端点可以从\(1 \ldots i\) 任意选择（共 \(i\) 种）。
• 右端点可以从 \(i \ldots n\) 任意选择（共 \(n – i + 1\) 种）。

    所以总贡献为： \(i \times (n – i + 1)\)

情况二：当 \(a_i \neq b_i\)

    设 \(need = \max(a_i, b_i)\)。
    为了让 \(z_i = b_i\) 且保持前缀最大值与 \(a\) 一致，必须在 \(i\) 之前存在一个位置 \(pos\)，满足： \(a_{pos} \ge need\)

    这样 \(z_i\)​ 才能合法取到 \(b_i\)。

    一旦找到这样的最早位置 \(pos\)，贡献就由它来决定：

• 左端点可选 \([1 \ldots pos]\)，数量为 \(pos\)。
• 右端点可选 \([i \ldots n]\)，数量为 \((n – i + 1)\)。

    因此贡献为： \(pos \times (n – i + 1)\)

实现方法

• 先把所有 \(a_i = b_i\) 的情况直接累加贡献。
• 对于 \(a_i \neq b_i\)​，记录需求 (need, i)，其中 \(need = \max(a_i, b_i)\)，表示“位置 \(i\) 需要一个 \(\ge need\) 的前缀”。
• 使用小根堆维护这些需求，并从右向左遍历数组：
  • 当扫到某个位置 \(i\) 时，如果 \(a_i \ge\) 堆顶的 \(need\)，说明该位置可以作为这批需求的最早前缀位置。
  • 由于是小根堆，满足条件的需求会连续出现在堆顶，所以可以用 while 循环批量弹出并计算贡献。
  • 每个弹出的需求 (need, y) 贡献为： \(i \times (n – y + 1)\)

    这样，就能在 \(O(n \log n)\) 时间内完成所有贡献的计算。

关键代码：

void solve()
{
    using namespace views;

    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (auto &x : a | drop(1))
        cin >> x;
    for (auto &x : b | drop(1))
        cin >> x;

    ll ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += (a[i] == b[i]) * (i * (n - i + 1ll));

    priority_queue<pii, vector<pii>, greater<pii>> q;
    for (int i = n; i; --i)
    {
        while (q.size() && q.top().first <= a[i])
        {
            auto [x, y] = q.top();
            q.pop();

            ans += i * (n - y + 1ll);
        }

        if (a[i] == b[i])
            continue;

        q.push({max(a[i], b[i]), i});
    }

    cout << ans << endl;
}

G. Cry Me a River

    还没补。