题目描述
有一个长度为 (n) 的序列，初始时序列中的数全为 (2^{31}-1)。
有 (m) 次操作，第 (i) 次操作为将序列中第 (a_i) 个数修改为 (b_i)。
记第 (i) 次操作后序列中的最小值为 (s_i)，你需要输出 (sumlimits_{i=1}^m s_i imes 10099^i)。
(a_i) 和 (b_i) 用以下方法确定：
输入整数 (x_0)、(x_1)、(a)、(b)、(c)，令 (x_i=(ax_{i-2}+bx_{i-1}+c) mod 2^{32}quad (ige 2))，则 (a_i=leftlfloordfrac{x_{2i-1}}{4} ight floor mod n)，(b_i=leftlfloordfrac{x_{2i}}{4} ight floor)。
输入格式
一行七个整数 (n)，(m)，(x_0)，(x_1)，(a)，(b)，(c)。
输出格式
一行一个整数表示答案。
数据范围
测试时间限制 (1000 mathrm{ms})，空间限制 (256 mathrm{MiB})。
- 对于 (10\%) 的数据，(1le n,mle 1000)；
- 对于 (50\%) 的数据，(1le n,mle 10^5)；
- 对于 (100\%) 的数据，(1le n,mle 10^7)，(x_0)、(x_1)，(a)，(b)，(c) 在 (left[0,2^{31}-1 ight)) 中均匀随机。
分析
注意到这题要求的操作很少，所以我们要考虑一些比较大胆的做法。
(mathtt{10 pts})
很简单，记录一个数组，每一次修改以后的暴力扫一遍最小值，复杂度 (Theta(1)-Theta(n))，稳稳超时。
(mathtt{50 pts})
也很简单，随便套一个 (mathcal{O}(log n)) 的数据结构乱搞就行了。
(mathtt{100 pts})
这个就有点难想到了。
根据数据范围，我们八成要设计一种查询 (Theta(1)) 的算法。也就是单纯的修改 (Theta(1))，查询 (Theta(1))。
在脑中搜刮一下后，好像支持修改、查询，修改是 (Theta(1)) 的就只有暴力了。
但在一般的题目中，毒瘤出题人都会设计数据卡暴力，使之在查询时跑得奇慢无比。
但是……我们发现，这题的操作都是伪随机生成的。难道……
考虑这样的算法：
维护数组 (A)，记录第 (i) 位的值 (A_i)。
修改：直接修改 (A_i)；
查询：
如果不是最小值所在的位置，则更新最小值和其所在位置。
如果是的话，则暴力更新最小值。
利用伪随机的性质，修改到最小值的概率为 (dfrac{m}{n})，则复杂度的数学期望
可以通过本题。
Code
顺带一提，这道题有点卡空间……开 long long 就炸了。
#include <cstdio>
#include <climits>
using namespace std;
typedef unsigned int ui;
const int max_n = 10000000;
const ui mul = 10099;
ui nums[max_n];
int main()
{
int n, m, min_pos = -1;
ui x0, x1, a, b, c, ans = 0, tk = 1, xt, ai, bi, min_val = INT_MAX;
scanf("%d%d%u%u%u%u%u", &n, &m, &x0, &x1, &a, &b, &c);
for (int i = 0; i < n; i++)
nums[i] = INT_MAX;
for (int i = 0; i < m; i++)
{
ai = (x1 / 4) % n;
xt = a * x0 + b * x1 + c;
bi = xt / 4, x0 = x1, x1 = xt;
xt = a * x0 + b * x1 + c;
x0 = x1, x1 = xt;
nums[ai] = bi;
if (ai == min_pos && bi > min_val)
{
min_val = INT_MAX, min_pos = -1;
for (int i = 0; i < n; i++)
if (nums[i] < min_val)
{
min_val = nums[i];
min_pos = i;
}
}
else if (bi < min_val)
{
min_val = bi;
min_pos = ai;
}
tk *= mul;
ans += tk * min_val;
}
printf("%u
", ans);
return 0;
}
后记
这道题告诉了我们一个很有意思的道理——复杂度越大，适用范围越广。
同样地，复杂度小的，适用范围会小一点。
解题时，一般要选择适合的算法，即题目在适用范围之内，而且复杂度较优。这题就是一个很好的例子。