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

86 阅读 0 评论 57 点赞

我是靠谱客的博主明理小笼包，最近开发中收集的这篇文章主要介绍[ 2-SAT 线段树 ] Codeforces Gym 100159 Facebook Hacker Cup 2012 I.Unfriending，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

%%%Manchery

题解

#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;
}