Happybob's Game
cosf
·
·
题解
「UOI」Beginner Contest 001 & Round 3 Happybob's Game
首先先说一下这一道题的数据范围。
$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](https://hydro.ac/d/uoi233/record/645f7123e3f1072df0b1db0c)
```cpp
#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}$。