[ 2-SAT 线段树 ] Codeforces Gym 100159 Facebook Hacker Cup 2012 I.Unfriending

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void Read(int& x){
char c=nc();
for(;c<'0'||c>'9';c=nc());
for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
}
inline void Read(ll& x){
char c=nc();
for(;c<'0'||c>'9';c=nc());
for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
}
#define N 50010
#define M 5000010
#define E 15000010
struct Node{
int w,f;
}a[N];
int T;
int i,j,k,n,m;
int A,B,p,l,r;
int y[N],num,pr[N],sf[N];
int ls[M],rs[M],Rt;
int dfn[M],low[M],tt,st[M],top,f[M],cnt;
int nx[E],t[E],h[M],H[M],tot;
bool b[N];
inline bool Cmp(Node a,Node b){
return a.w<b.w;
}
inline void Dfs(int x){
low[x]=dfn[x]=++tt;st[++top]=x;
for(int i=h[x];i;i=nx[i]){
int v=t[i];
if(!dfn[v])Dfs(v),low[x]=min(low[x],low[v]);else
if(!f[v])low[x]=min(low[x],dfn[v]);
}
if(low[x]==dfn[x]){
++cnt;
while(st[top]!=x)f[st[top--]]=cnt;
f[st[top--]]=cnt;
}
}
inline bool Tarjan(){
for(int i=1;i<=num;i++)dfn[i]=f[i]=0;tt=cnt=0;
for(int i=1;i<=num;i++)if(!dfn[i])Dfs(i);
for(int i=1;i<=n;i++)if(f[i<<1]==f[i*2-1])return 0;
return 1;
}
inline void Add(int x,int y){
t[++tot]=y;nx[tot]=h[x];h[x]=tot;
}
inline void Add(int x,int l,int r,int L,int R,int y){
if(l>R||r<L)return;
if(l>=L&&r<=R){
Add(y,x);
return;
}
int Mid=l+r>>1;
Add(ls[x],l,Mid,L,R,y);Add(rs[x],Mid+1,r,L,R,y);
}
inline bool Check(int x){
int j=1,s=0;
for(int i=1;i<=n;i++){
for(;j<n&&a[j+1].w-a[i].w<x;j++);
s+=j-i;
}
if(s>1200000)return 0;
for(int i=1;i<=num;i++)H[i]=h[i];
int Tot=tot;
j=1;
for(int i=1;i<=n;i++){
for(;j<n&&a[j+1].w-a[i].w<x;j++);
Add(Rt,1,n,i+1,j,a[i].f<<1);
}
j=n;
for(int i=n;i;i--){
for(;j>1&&a[i].w-a[j-1].w<x;j--);
Add(Rt,1,n,j,i-1,a[i].f<<1);
}
bool f=Tarjan();
tot=Tot;
for(int i=1;i<=num;i++)h[i]=H[i];
return f;
}
inline void Build(int& x,int l,int r){
x=++num;
if(l==r){
Add(x,a[l].f*2-1);
return;
}
int Mid=l+r>>1;
Build(ls[x],l,Mid);Build(rs[x],Mid+1,r);
Add(x,ls[x]);Add(x,rs[x]);
}
int main(){
Read(T);
for(int TT=1;TT<=T;TT++){
Read(n);Read(m);
Read(a[1].w);Read(A);Read(B);Read(p);a[1].f=1;b[1]=0;
for(i=2;i<=n;i++)a[i].w=(1ll*a[i-1].w*A+B)%p,a[i].f=i,b[i]=0;
for(i=1;i<=num;i++)h[i]=0;tot=0;
num=(n<<1);
for(i=1;i<=m;i++){
Read(k);Read(y[1]);Read(A);Read(B);
for(j=2;j<=k;j++)y[j]=(1ll*y[j-1]*A+B)%n;
sort(y+1,y+k+1);k=unique(y+1,y+k+1)-y-1;
for(j=1;j<=k;j++)pr[j]=++num,sf[j]=++num,b[++y[j]]=1;
for(j=1;j<=k;j++){
if(j>1)Add(y[j]*2-1,pr[j-1]),Add(pr[j],pr[j-1]);
if(j<k)Add(y[j]*2-1,sf[j+1]),Add(sf[j],sf[j+1]);
Add(pr[j],y[j]<<1);Add(sf[j],y[j]<<1);
}
}
for(i=1;i<=n;i++)if(!b[i])Add(i*2-1,i<<1);
sort(a+1,a+n+1,Cmp);
Build(Rt,1,n);
l=1;r=a[n].w-a[1].w;
while(l<=r){
int Mid=l+r>>1;
if(l<10&&r>10)Mid=10;
if(Check(Mid))l=Mid+1;else r=Mid-1;
}
printf("Case #%d: %dn",TT,r);
}
return 0;
}