[NOI2014] 随机数生成器

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXNM = 5000;
const int INF = 0x3f3f3f3f;
int x0;
ll a, b, c, d;
int n, m, q;
// int x[MAXNM * MAXNM + 5];
int T[MAXNM * MAXNM + 5];
int get(int x, int y)
{
    return T[(x - 1) * m + y];
}
// 数字 i 所在的位置是 id[i];
int id[MAXNM * MAXNM + 5];
// 第 i 行的可选范围是 canL[i] canR[i]
int canL[MAXNM + 5], canR[MAXNM + 5];
vector<int> ans;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> x0 >> a >> b >> c >> d;
    cin >> n >> m >> q;
    // x[0] = x0;
    T[0] = x0;
    for (int i = 1; i <= n * m; i++)
    {
        // x[i] = (a * x[i - 1] * x[i - 1] + b * x[i - 1] + c) % d;
        // T[i] = i;
        T[i] = (a * T[i - 1] * T[i - 1] + b * T[i - 1] + c) % d;
    }
    for (int i = 1; i <= n * m; i++)
    {
        // swap(T[i], T[T[i] % i + 1]);
        int pos = T[i] % i + 1;
        T[i] = T[pos];
        T[pos] = i;
    }
    while (q--)
    {
        int ui, vi;
        cin >> ui >> vi;
        swap(T[ui], T[vi]);
    }
    /*
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cout << get(i, j) << " ";
        cout << "\n";
    }
    */
    for (int i = 1; i <= n; i++)
    {
        canL[i] = 1, canR[i] = m;
        for (int j = 1; j <= m; j++)
        {
            int now = get(i, j);
            id[now] = i * (m + 1) + j;
        }
    }
    for (int i = 1; i <= n * m; i++)
    {
        int nowX = id[i] / (m + 1);
        int nowY = id[i] % (m + 1);
        // 执行 N*M 次
        if (canL[nowX] <= nowY && nowY <= canR[nowX])
        {
            // 下面的for最多被执行 N+M-1 次，每次都是 O(n)，能过
            for (int row = 1; row < nowX; row++)
                canR[row] = min(canR[row], nowY);
            for (int row = nowX + 1; row <= n; row++)
                canL[row] = max(canL[row], nowY);
            ans.push_back(i);
        }
    }
    for (int id : ans)
        cout << id << " ";
    cout << "\n";
    return 0;
}
// x[i] = (ax[i-1]^2 + bx[i-1] + c) % d