洛谷P2354 [NOI2014] 随机数生成器 题解
题意：
小 H 最近在研究随机算法。随机算法往往需要通过调用随机数生成函数（例如 Pascal 中的
random和 C/C++中的rand）来获得随机性。事实上，随机数生成函数也并不是真正的“随机”，其一般都是利用某个算法计算得来的。比如，下面这个二次多项式递推算法就是一个常用算法：
算法选定非负整数 \(x_0,a,b,c,d\) 作为随机种子，并采用如下递推公式进行计算。
对于任意 \(i \ge 1,x_i=(a \times x_{i-1}^2+b \times x_{i-1}+c)\bmod d\) 这样可以得到一个任意长度的非负整数数列\(\{x_i\},i \ge 1\)，一般来说，我们认为这个数列是随机的。
利用随机序列 \({xi},i\ge\)，我们还可以采用如下算法来产生一个 \(1\) 到 \(K\) 的随机排列\(\{ T_i \},~i=1 ... k\)：
1、初始设 \(T\) 为 \(1\) 到 \(K\) 的递增序列；
2、对 \(T\) 进行 \(K\) 次交换，第 \(i\) 次交换，交换 \(T_i\) 和 \(T_{(x_i \bmod i) + 1}\) 的值。
此外，小 H 在这 \(K\) 次交换的基础上，又额外进行了 \(Q\) 次交换操作，对于第 \(i\) 次额外交换，小 H 会选定两个下标 \(u_i\) 和 \(v_i\)，并交换 \(T_{u_i}\) 和 \(T_{v_i}\) 的值。
为了检验这个随机排列生成算法的实用性，小 H 设计了如下问题：
小 H 有一个 \(N\) 行 \(M\) 列的棋盘，她首先按照上述过程，通过 \(N \times M + Q\) 次交换操作，生成了一个 \(1\sim N \times M\) 的随机排列 \(\{Ti\},i=1 ... N \times M\)，然后将这 \(N \times M\) 个数逐行逐列依次填入这个棋盘：也就是第 \(i\) 行第 \(j\) 列的格子上所填入的数应为 \(T_{(i-1) \times M+j}\)。
接着小 H 希望从棋盘的左上角，也就是第一行第一列的格子出发，每次向右走或者向下走，在不走出棋盘的前提下，走到棋盘的右下角，也就是第 \(N\) 行第 \(M\) 列的格子。
小 H 把所经过格子上的数字都记录了下来，并从小到大排序，这样，对于任何一条合法的移动路径，小 H 都可以得到一个长度为 \(N + M - 1\) 的升序序列，我们称之为路径序列。
小 H 想知道，她可能得到的字典序最小的路径序列应该是怎样的呢？
输入格式：
第 \(1\) 行包含 \(5\) 个整数，依次为 \(x_0,a,b,c,d\) ，描述 cxy 采用的随机数生成算法所需的随机种子。
第 \(2\) 行包含三个整数 \(N,M,Q\) ，表示 cxy 希望生成一个 \(1\) 到 \(N \times M\) 的排列来填入她 \(N\) 行 \(M\) 列的棋盘，并且 cxy 在初始的 \(N \times M\) 次交换操作后，又进行了 \(Q\) 次额外的交换操作。
接下来 \(Q\) 行，第 \(i\) 行包含两个整数 \(u_i,v_i\)，表示第 \(i\) 次额外交换操作将交换 \(T_{u_i}\)和 \(T_{v_i}\) 的值。
输出格式：
输出一行，包含 \(N+M-1\) 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。
数据范围：
\(2 \le N,M \le 5000,~0\le Q \le 5\times 10^4,~0\le a \le 300\)
\(0 \le b,c \le 10^8,~0 \le x_0 < d \le 10^8,~1 \le u_i,v_i \le N \times M\)
以为要研究什么随机数的性质，结果就是给了个随机数生成器叫我们模拟。
总之就是生成了一个 \(r\times c\) 的排列，贪心地选择最小的数即可。
现在的问题是怎么判断能不能选。注意到每次放置一个数到 \((x,y)\) ，图中红色区域的数都不能放了
因此我们可以维护个 \(\mathtt{le[i],ri[i]}\) ，表示每一行可选的数的区间
显然这个 \(\mathtt{le[i],ri[i]}\)
是单调递增的，因此当 \(\mathtt{ri[i]}\le
y\) 时，就可以直接 return 0 了。
时间复杂度 \(\mathcal{O}(r\times c + r^2)\)
代码：
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2.5e7+15))
#define M ((int)(5e3+15))
struct cxy
{
int x,a,b,c,d;
void init() { cin >> x >> a >> b >> c >> d; }
int get() { return x = (int)((((ll)a * x + b) * x + c) % d); }
}rnd;
int r,c,cnt,Q;
int T[N],t[N],le[N],ri[N];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
rnd.init(); cin >> r >> c >> Q;
for(int i = (cnt = r * c); i; i--) T[i] = i;
for(int i=1; i<=cnt; i++) swap(T[i], T[rnd.get() % i + 1]);
for(int u,v; Q--; ) { cin >> u >> v; swap(T[u], T[v]); }
for(int i=1; i<=cnt; i++) t[T[i]] = i;
for(int i=0; i<r; i++) { le[i] = 1; ri[i] = c; }
for(int i=1,u,v,w; i<=cnt; i++)
{
w = t[i]; u = (w - 1) / c; v = w - u * c;
if(le[u] <= v && v <= ri[u])
{
cout << i;
if(++Q == r + c - 1) return cout << '\n',0;
cout << ' ';
for(int j=u-1; j >= 0 && ri[j] > v; --j) ri[j] = v;
for(int j=u+1; j<r && le[j] < v; ++j) le[j] = v;
}
}
return 0;
}参考文献：
