3671: [Noi2014]随机数生成器
Time Limit: 50 Sec Memory Limit: 256 MB
Submit: 1907 Solved: 854
Description
Input
第1行包含5个整数，依次为 x_0,a,b,c,d ，描述小H采用的随机数生成算法所需的随机种子。第2行包含三个整数 N,M,Q ，表示小H希望生成一个1到 N×M 的排列来填入她 N 行 M 列的棋盘，并且小H在初始的 N×M 次交换操作后，又进行了 Q 次额外的交换操作。接下来 Q 行，第 i 行包含两个整数 u_i,v_i，表示第 i 次额外交换操作将交换 T_(u_i )和 T_(v_i ) 的值。
Output
输出一行，包含 N+M-1 个由空格隔开的正整数，表示可以得到的字典序最小的路径序列。
Sample Input
1 3 5 1 71
3 4 3
1 7
9 9
4 9
Sample Output
1 2 6 8 9 12
HINT
本题的空间限制是 256 MB，请务必保证提交的代码运行时所使用的总内存空间不超过此限制。
一个32位整数（例如C/C++中的int和Pascal中的Longint）为4字节，因而如果在程序中声明一个长度为 1024×1024 的32位整型变量的数组，将会占用 4 MB 的内存空间。
2≤N,M≤5000
0≤Q≤50000
0≤a≤300
0≤b,c≤108
0≤x0<d≤1081≤ui,vi≤N×M
Source
【分析】
破题想一年系列。
首先把这玩意造出来，然后贪心的取，发现取完一个之后它左下角和右上角的部分都要ban掉。
怎么ban啊
想了各种傻逼做法什么树状数组线段树。
最后发现它真正取得只有O(n)级别个数。不取的必须做到O(1)ban掉。
那取得时候对于每列开个数组记录从上到下ban的最远处和从下到上ban的最远处就完了。
我真是个煞唉
这题还卡空间，用了个short
【代码】
//洛谷 P2354 随机数生成器
#include<bits/stdc++.h>
#define p(i,j) (i-1)*m+j
#define LL long long
#define M(a) memset(a,0,sizeof a)
#define fo(i,j,k) for(i=j;i<=k;i++)
using namespace std;
const int mxn=5005;
int n,m,Q,a,b,c,d,cnt;
short y[mxn*mxn];
int ans[mxn<<1];
int up[mxn],low[mxn];
int T[mxn*mxn],x[mxn*mxn];
int main()
{
int i,j,u,v;
scanf("%d%d%d%d%d",&x[0],&a,&b,&c,&d);
scanf("%d%d%d",&n,&m,&Q);
fo(i,1,n*m) T[i]=i;
fo(i,1,n*m) x[i]=(LL)((LL)a*x[i-1]%d*x[i-1]%d+(LL)b*x[i-1]%d+(LL)c)%d;
fo(i,1,n*m) swap(T[i],T[x[i]%i+1]);
while(Q--) scanf("%d%d",&u,&v),swap(T[u],T[v]);
fo(i,1,n) fo(j,1,m) x[T[p(i,j)]]=i,y[T[p(i,j)]]=j;
fo(j,1,m) low[j]=n+1;
fo(i,1,n*m)
{
if(up[y[i]]>=x[i] || low[y[i]]<=x[i]) continue;
ans[++cnt]=i;
fo(j,1,y[i]-1) low[j]=min(low[j],x[i]+1);
fo(j,y[i]+1,m) up[j]=max(up[j],x[i]-1);
if(cnt==n+m-1) break;
}
// sort(ans+1,ans+cnt+1);
fo(i,1,cnt-1) printf("%d ",ans[i]);
printf("%d\n",ans[cnt]);
return 0;
}