洛谷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;
}参考文献：
