自动搬运

查看原文

来自洛谷，原作者为

	cosf 省选挂48分

搬运于2025-08-24 23:02:34，当前版本为作者最后更新于2023-04-07 20:34:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

「UOI」Beginner Contest 001 & Round 3 Happybob's Game

首先先说一下这一道题的数据范围。

$1 \le n \le 5 \times 10^6$，$O(n\log n)$ 会比较吃力，故这题是常数比较大的 $O(n)$。

$1 \le q \le 10^5$，显然大约是 $O(q\log n)$ 这个量级的。

故我的做法复杂度是 $O(n + q(1 + \log n + \log sum))$（$1, \log n, \log sum$ 分别对应操作 $1, 2, 3$）。

---

思路

我们先考虑操作 $3$。

如果只有操作 $3$，则相当于 $a_i$ 和 $m_i$ 是定值。原来的题是这样的，不过太水，所以加了询问。

我们要求 $a_i$ 在以 $m_i$ 为分母时的能存活的天数，相当于求以 $m_i$ 为分母过多少天至少需要的人数为 $\sum a_i = sum$。

换句话说，就是求能活 $k$ 天的最少军队人数。令其为 $d_k$。若存在一 $k$ 使得 $d_{k - 1} \le sum \lt d_k$，则 $k-1$ 就是所求的答案。

因为每分钟都可以任意地调换军队的人，所以 $a_i$ 的具体内容是不重要的，只需记录它的和，令设 $1 \le m_1 \le \dots \le m_n$。

显然 $\{d_k\}$ 存在递推关系，$d_1 = \sum m_i$。

那么，$d_{k+1} = \sum_{i=1}^n m_id_{k,i}$，其中 $d_{k, i}$ 为和为 $d_k$ 的正整数列。

容易证明，$d_{k, 2} = d_{k, 3} = \dots = d_{k, n} = 1, d_{k, 1} = d_k - n + 1$ 时 $d_{k + 1}$ 取到最小值 $m_1(d_k - n + 1) + (\sum_{i=1}^n m_i - m_1) = m_1(d_k - n) + \sum_{i=1}^n m_i$。

那么，我们可以得出 $\{d_k\}$ 的通项公式：

$$d_k = nm_1^k + \frac{m_1^k - 1}{m_1 - 1}(\sum_{i=1}^n m_i - m_1) $$

显然，当 $m_1 \gt 1$ 时这是个（快于）指数级增长的数列，故时间复杂度 $\gt O(\log_{m_1}sum) \ge O(\log sum)$。可以优化到 $O(\log\log sum)$，不过没必要。

当 $m_1 = 1$ 时可以直接解一元一次方程，复杂度为 $O(1)$。

至此，操作 $3$ 已经考虑完毕。

显然（又是显然），操作 $1$ 只需要简单地维护一下 $a_i$ 的值（修改需要记录差）和 $sum$ 就可以了。

而操作 $2$ 则需要用一些特殊的数据结构维护最小值（达到 $O(1)$ 插入和算 min）。

这可以用配对堆等数据结构完成。set 维护前 $q$ 大也可行，也可以过，也好写，但比我这个慢一点。

最后，参考代码：

AC Code

#include <iostream>
#include <cstdlib>
using namespace std;
inline long long read() {} // 快读
template <typename T = int, typename C = less<int>, int S = 1000006> class Heap {}; // 堆

long long as;
long long a[5000006];
Heap<int, less<int>, 5000006> mt; // 堆
long long sm;

int main()
{
    int n = read(), q = read();
    for (int i = 1; i <= n; i++)
    {
        as += a[i] = read();
    }
    long long mi;
    for (int i = 1; i <= n; i++)
    {
        mi = read();
        mt.push(mi);
        sm += mi;
    }
    while (q--)
    {
        int op = read(), i, x;
        if (op == 1)
        {
            i = read();
            x = read();
            as = as - a[i] + x;
            a[i] = x;
        }
        else if (op == 2)
        {
            i = read();
            x = read();
            sm = sm - mt.dts[i]->a + x;
            mt.modify(mt.dts[i], x);
        }
        else if (op == 3) // 注意递推的公式
        {
            long long mm = mt.top();
            long long ca = as;
            if (sm == n)
            {
                if (ca >= n)
                    cout << -1 << endl;
                continue;
                cout << 0 << endl;
            }
            else if (mm == 1)
            {
                ca -= n;
                ca /= (sm - n);
                cout << ca << endl;
                continue;
            }
            long long mc = -1;
            long long cur = n;
            while (cur <= ca)
            {
                mc++;
                cur = cur * mm + sm - mm * n;
            }
            cout << mc << endl;
        }
    }
    return 0;
}

运行时间和空间：$\textsf{350ms, 300MiB}$。