bzoj 3671 随机数生成器 —— 暴力

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3671

原来256M是可以开两个3e7的数组的；

因为答案只有 n+m-1 个数，所以暴力判断能否放即可，不用线段树；

然而 O(n) 判断 O(1) 修改和 O(1) 判断 O(n) 修改是不同的。呵呵。

代码如下：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int const xn=5005,xxn=25000005,xm=5e4+5;
int n,m,t[xxn],ps[xxn],mn[xn],mx[xn];
int rd()
{
  int ret=0,f=1; char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}
  while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
  return f?ret:-ret;
}
int mnn(int x,int y){return x<y?x:y;}
int mxx(int x,int y){return x<y?y:x;}
int main()
{
  int xx=rd(),a=rd(),b=rd(),c=rd(),d=rd();
  n=rd(); m=rd(); int Q=rd();
  for(int i=1;i<=n*m;i++)t[i]=i;
  for(int i=1;i<=n*m;i++)
    {
      xx=((ll)a*xx*xx+(ll)b*xx+c)%d;//!%d
      swap(t[i],t[xx%i+1]);
    }
  for(int i=1,u,v;i<=Q;i++)u=rd(),v=rd(),swap(t[u],t[v]);
  for(int i=1;i<=n*m;i++)ps[t[i]]=i;
  for(int i=1;i<=m;i++)mn[i]=1,mx[i]=n;
  int num=0;
  for(int i=1,x,y;i<=n*m;i++)
    {
      x=(ps[i]-1)/m+1; y=(ps[i]-1)%m+1;
      if(mn[y]>x||mx[y]<x)continue;
      printf("%d ",i); num++;
      if(num==n+m-1)break;
      for(int i=1;i<y;i++)mx[i]=mnn(mx[i],x);
      for(int i=y+1;i<=m;i++)mn[i]=mxx(mn[i],x);
    }
  puts("");
  return 0;
}