题解 CF1810H Last Number

kyEEcccccc · 2023-06-21 14:01:24 · 题解

大难题，但是非常的有意思。思路来自 艾利克斯·伟。补充了一点小细节。

题意

对于一个可重集合 S，初始为 \{1 \dots n\}，执行以下操作：删除集合中的最大、最小元素 S_{min}, S_{max}，加入 S_{max} - S_{min}。最终集合只剩下一个元素，输出这个元素。

给定 T 组 n，分别输出答案，1 \le T \le 10^5, 1 \le n \le 10^9。

做法

首先观察题目给出的操作序列，容易发现这些操作是分为两部分的。记第 i 次操作加入的是 a_i - b_i。存在一个 p 使得 \forall 1 \le i < p，a_i > 2b_i，并且 a_p \le 2b_p。那么 \forall 1 \le i \le p, b_i = i, a_{i-1} - a_i \in \{0, 1\}，看起来是很可以做的。

这部分先按下不表，转而考察 p < i \le n-1 的情况。记第 p 次操作以后的可重集合是 S'，同时也记它为集合排序后的序列。那么容易得出此时的每次操作以后，新集合的最小值一定是刚加入的数。这个直觉的来源是，加入的数整体而言在不断变小。事实上可以证明，由于最大值不减，所以每两轮，加入的数一定不减；而第 p 和 p+1 次操作都保证生成的数是集合最小值——所以接下来的过程中它始终保持最小。有了这个结论，我们可以优美地描述后半部分操作：Ans = S'_2 - (S'_3 - (S'_4 - \dots (S'_{n-p} - S'_1)\dots))。

接下来，考虑前半部分操作。首先，b_i = i, a_{i-1} - a_i \in \{0, 1\} 告诉我们，每一次生成的数都会变小 1 或 2。那么从大到小扫描值域的过程中，每次碰到的数都要么有一个要么有两个。一旦生成了一个数，这个数和它后面的所有数的个数都确定下来了。所以考虑依次确定这些数的个数。记 d_i = a_{i-1}-a_i，则若 d_i = 0，被确定的数是 a_i - i 有两个；否则被确定的是 a_i - i 有两个，a_i - i + 1 有一个。考虑维护 d 而不是 a。那么相当于我扫描到一个 0 就加入 10，扫描到一个 1 就加入 110。考虑 d 序列的前几项：

0/10/11010/1101101011010/...

你可以把生成 d 的过程分段化，设 Q_i 表示第 i 阶段生成的串，那么它前缀依次拼接得到的就是 d 序列。Q_{i+1} 是由 Q_i 中所有 0 替换成 10，所有 1 替换成 110 得到的。生成这种东西，不要依次递推，而是考虑从开头插入操作。具体地，记 f_{0/1, i} 表示一开始为 0/1 进行 i 次迭代得到的东西，那么 Q_i = f_{0, i}。则存在递推：

\begin{cases} f_{0, i} = f_{1, i-1} + f_{0, i-1}\\ f_{1, i} = f_{1, i-1} + f_{1, i-1} + f_{0, i-1} \end{cases}

那么我们就获得了一种优雅的方法生成 Q，可以借此获得 d 的前缀信息。

接下来，只需要结合上面对于后半部分操作的结论即可。容易得出，考虑我们在第 p 次操作结束后生成的 d 所对应的 a 序列。则上述的 S'_1 = a_p - p \le p，而 S'_i = a_{n-i+1}(2 \le i \le n-p)。所以：

\begin{aligned} Ans &= a_{n-1} - (a_{n-2} - (a_{n-3} - \dots (a_{p+1} - (a_p - p))\dots))\\ &= (-1)^{n-p}p +\sum\limits_{i = p}^{n-1} (-1)^{n-i+1}a_i\\ &= \begin{cases} p - (a_p - a_{p+1}) - (a_{p+2} - a_{p+3}) - \dots - (a_{n-2} - a_{n-1}), & 2|(n-p)\\ a_p - p - (a_{p+1} - a_{p+2}) - (a_{p+3} - a_{p+4}) - \dots - (a_{n-2} - a_{n-1}); & \text{otherwise} \end{cases}\\ &= \begin{cases} p - (d_{p+1} + d_{p+3} + d_{p+5} + \dots + d_{n-1}), & 2|(n-p)\\ \left(n - \sum\limits_{i=1}^{p} d_i\right) - p - (d_{p+2} + d_{p+4} + d_{p+6} + \dots + d_{n-1}); & \text{otherwise} \end{cases} \end{aligned}

那么我们要支持快速求 d 序列的前缀和，前缀偶数项和，前缀奇数项和。刚刚说了优雅地生成 d 数列的方法。那么直接维护这些信息即可。注意到我们用来拼接成 d 的 Q 序列最后一项可能是不完整的，这时候去考虑那个递推式子，直接递归往下拆，每次只会递归到其中一侧，时间复杂度还是单 \log。另外一个事情是求 p 可以不用二分双 \log，用类似线段树上二分的手段即可。

代码

// Author: kyEEcccccc

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
using ULL = unsigned long long;

#define F(i, l, r) for (int i = (l); i <= (r); ++i)
#define FF(i, r, l) for (int i = (r); i >= (l); --i)
#define MAX(a, b) ((a) = max(a, b))
#define MIN(a, b) ((a) = min(a, b))
#define SZ(a) ((int)((a).size()) - 1)

constexpr int K = 23;

struct SegInfo
{
    int len, odd, even, sum;

    SegInfo operator +(const SegInfo& o)
    const {
        if (len % 2 == 0) return {len + o.len, odd + o.odd, even + o.even, sum + o.sum};
        else return {len + o.len, odd + o.even, even + o.odd, sum + o.sum};
    }
};

SegInfo f[2][K];

void init(void)
{
    f[0][0] = {1, 0, 0, 0};
    f[1][0] = {1, 1, 0, 1};
    F(i, 1, K - 1)
    {
        f[0][i] = f[1][i - 1] + f[0][i - 1];
        f[1][i] = f[1][i - 1] + f[1][i - 1] + f[0][i - 1];
    }
    int sum = 0;
    F(i, 0, K - 1) sum += f[0][i].len;
}

int find_p(int n)
{
    SegInfo all = {0, 0, 0, 0};
    F(i, 0, K - 1)
    {
        SegInfo nw = all + f[0][i];
        if (n - nw.sum <= 2 * nw.len)
        {
            int t = 0;
            FF(j, i - 1, 0)
            {
                if (t == 0)
                {
                    nw = all + f[1][j];
                    if (n - nw.sum <= 2 * nw.len) t = 1;
                    else
                    {
                        t = 0;
                        all = nw;
                    }
                }
                else
                {
                    nw = all + f[1][j];
                    if (n - nw.sum <= 2 * nw.len) t = 1;
                    else
                    {
                        all = nw;
                        nw = all + f[1][j];
                        if (n - nw.sum <= 2 * nw.len) t = 1;
                        else
                        {
                            t = 0;
                            all = nw;
                        }
                    }
                }
            }
            return all.len + 1;
        }
        all = nw;
    }
    assert(0);
}

SegInfo getinfo(int m)
{
    SegInfo all = {0, 0, 0, 0};
    F(i, 0, K - 1)
    {
        if (all.len + f[0][i].len < m)
        {
            all = all + f[0][i];
            continue;
        }
        int t = 0;
        FF(j, i - 1, 0)
        {
            if (t == 0)
            {
                if (all.len + f[1][j].len >= m) t = 1;
                else
                {
                    t = 0;
                    all = all + f[1][j];
                }
            }
            else
            {
                if (all.len + f[1][j].len >= m) t = 1;
                else
                {
                    all = all + f[1][j];
                    if (all.len + f[1][j].len >= m) t = 1;
                    else
                    {
                        t = 0;
                        all = all + f[1][j];
                    }
                }
            }
        }
        return all + f[t][0];
    }
    assert(0);
}

void work(void)
{
    int n; cin >> n;
    if (n == 1) return cout << "1\n", void();
    if (n == 2) return cout << "1\n", void();
    int p = find_p(n);
    SegInfo xp = getinfo(p), xn = getinfo(n - 1);
    if ((n - p) % 2 == 0)
    {
        if (p % 2 == 0) cout << p - xn.odd + xp.odd << '\n';
        else cout << p - xn.even + xp.even << '\n';
    }
    else
    {
        if (p % 2 == 0) cout << n - xp.sum - p - xn.even + xp.even << '\n';
        else cout << n - xp.sum - p - xn.odd + xp.odd << '\n';
    }
}

signed main(void)
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    ios::sync_with_stdio(0), cin.tie(nullptr);

    init();

    int _; cin >> _;
    while (_--) work();

    return 0;
}