【NOI2014】随机数生成器___带技巧的枚举+思维

题目大意：

题解：

这题MLE到我怕….
①为了防止MLE所以要重复利用同一个数组，5000*5000至多开2个！
②将横轴坐标用一个数存下来比如(i-1)*m+j，查询时再拆开，直接存会炸。

因为最后的Ti大小是在1~N*M之间的，而且要使得字典序最小，
那么能放最小的就尽可能放最小的，
不妨枚举1~N*M，
首先，将1~N*M的位置存下来，
对于一个路径而言，T[1,1]，T[N,M]是肯定存在的，而他们大小是不确定的，所以枚举i时判断一下
对于一个枚举到的i，答案已经有j个了，它所对应的坐标[x,y]是否合法，就判断是否与j个答案坐标冲突，直接判断冲突肯定会TLE，所以我们设minl[],minr[]表示某一行能放的列的范围，这个会随着答案的增加而被更新，此时判断y是否在[minl[x],minr[x]]中，在则代表是合法的，加入路径中。
当答案存在N+M-1个时，就可以直接输出了，不过因为你枚举到的n+m-1-2个 答案大小是按顺序的，
但你已知的T[1,1],T[N,M]的大小不是固定的..
所以你要判断，我懒直接套快排了，但其实顺序只受这2个影响..

代码：

const
         maxn=5001;

var
         minl,minr:Array [0..maxn] of longint;
         rp:Array [0..maxn*maxn,1..2] of longint;
         op:Array [0..2*maxn] of longint;
         y1,x,y,a,b,c,d,t,i,j,k,l,n,m,q:longint;
         a1,b1:longint;
         check:boolean;
         x1:int64;

function getx(aa:longint):longint;
begin
        getx:=aa div m;
        if getx=0 then exit(1);
        if aa mod m<>0 then exit(getx+1);
        exit(getx);
end;

function gety(aa:longint):longint;
begin
        gety:=aa mod m;
        if gety=0 then exit(m);
        exit(gety);
end;

procedure qsort(l,r:longint);
var
        i,j,mid:longint;
begin
        if l>=r then exit;
        i:=l; j:=r;
        mid:=op[(l+r) div 2];
        repeat
              while (op[i]<mid) do inc(i);
              while (op[j]>mid) do dec(j);
              if i<=j then
                 begin
                      op[0]:=op[i];
                      op[i]:=op[j];
                      op[j]:=op[0];
                      inc(i); dec(j);
                 end;
        until i>j;
        qsort(i,r);
        qsort(l,j);
end;

begin
         readln(x1,a,b,c,d);
         readln(n,m,q);
         for i:=1 to n*m do rp[i,1]:=i;
         for i:=1 to n*m do
              begin
                     x1:=((a*sqr(x1)+b*x1+c) mod d);
                     y1:=x1 mod i+1;
                     t:=rp[i,1];
                     rp[i,1]:=rp[y1,1];
                     rp[y1,1]:=t;
              end;

         for i:=1 to q do
            begin
                 readln(x,y);
                 t:=rp[x,1];
                 rp[x,1]:=rp[y,1];
                 rp[y,1]:=t;
            end;

         for i:=1 to n*m do
              rp[rp[i,1],2]:=i;

         for i:=1 to n do
             begin
                   minl[i]:=1;
                   minr[i]:=m;
             end;

         op[1]:=rp[1,1];
         op[2]:=rp[n*m,1];

         i:=2;

         for k:=1 to n*m do
           if k<>op[1] then
              if k<>op[2] then
              begin
                    a1:=getx(rp[k,2]);
                    b1:=gety(rp[k,2]);

                    if (b1>=minl[a1]) and (b1<=minr[a1])
                       then begin
                                 inc(i);
                                 op[i]:=k;
                                 for j:=1 to a1-1 do
                                     if minr[j]>b1 then minr[j]:=b1;
                                 for j:=a1+1 to n do
                                     if minl[j]<b1 then minl[j]:=b1;
                            end;
                    if i=n+m-1 then break;
              end;

         qsort(1,i);
         for j:=1 to i do write(op[j],' ');
end.