vfk说分不清noi2014和noip2014果然是有道理的……
因为要求字典序最小，可以直接从小到大枚举每个数，如果能加进字典序中，就贪心地加进去，正确性显然.
现在问题是怎么判断一个数能否加在当前的字典序里面. 注意到一条路径合法等价于它的横坐标和纵坐标均单调不减，维护$c _i$和$d _i$表示当前已经加进去的点中，横坐标为$i$的点的最小值和最大值. 每次加入一个点，先用zkw线段树找出小于它的最大的横坐标和大于它的最小的横坐标，假设为$j$和$k$，判断它的纵坐标是否在$d _j$和$c _k$之间即可.
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
using namespace std;
const ele M=1<<13;
const ele size=M<<1;
ele n,m,Q,x0,A,B,C,D,a[maxn*maxn],p[maxn*maxn],c[maxn],d[maxn],ans[maxn+maxn];
bool b[size];
inline void maintain(ele i){
b[i]=b[i<<1]|b[i<<1|1];
}
inline void upd(ele i){
i+=M; b[i]=true;
while (i>1) maintain(i>>=1);
}
ele _getl(ele i){
return i>=M?i-M:(b[i<<1|1]?_getl(i<<1|1):_getl(i<<1));
}
ele getl(ele i){
return (i&1) && b[i^1]?_getl(i^1):getl(i>>1);
}
ele _getr(ele i){
return i>=M?i-M:(b[i<<1]?_getr(i<<1):_getr(i<<1|1));
}
ele getr(ele i){
return (~i&1) && b[i^1]?_getr(i^1):getr(i>>1);
}
inline bool test(ele i){
ele x=p[i]/m+1,y=p[i]%m+1;
ele j=getl(x+M),k=getr(x+M);
return d[j]<=y && y<=c[k];
}
int main(){
scanf("%d%d%d%d%d%d%d%d",&x0,&A,&B,&C,&D,&n,&m,&Q);
for (int i=0; i<n*m; ++i) a[i]=i;
for (int i=1; i<=n*m; ++i){
x0=((ll)A*x0%D*x0%D+(ll)B*x0%D+C)%D;
swap(a[i-1],a[x0%i]);
}
while (Q--){
ele u,v;
scanf("%d%d",&u,&v);
swap(a[u-1],a[v-1]);
}
for (int i=0; i<n*m; ++i) p[a[i]]=i;
memset(b,0,sizeof(b));
b[0+M]=b[n+1+M]=true;
for (int i=M-1; i; --i) maintain(i);
memset(c,-1,sizeof(c)); memset(d,-1,sizeof(d));
c[0]=d[0]=0; c[n+1]=d[n+1]=m+1;
ele cnt=0;
for (int i=0; i<n*m && cnt<n+m-1; ++i)
if (test(i)){
ans[cnt++]=i;
ele x=p[i]/m+1,y=p[i]%m+1;
if (~c[x]) c[x]=min(c[x],y),d[x]=max(d[x],y);
else c[x]=d[x]=y;
upd(x);
}
for (int i=0; i<n+m-1; ++i) printf(i?" %d":"%d",ans[i]+1);
puts("");
return 0;
}