Fork me on GitHub

Uoj#356.【JOI2017春季合宿】Port Facility

Uoj#356.【JOI2017春季合宿】Port Facility 题解

题意:

  • 两个栈,给出$n$个元素的入出栈顺序,求合法入栈方案数。
  • $1\le n\le 10^6$。

题解:

  • 每个元素可以看做一个区间$[l_i,r_i]$。
  • 两个元素只有当$l_i<l_j<r_i<r_j$时必须分在两个栈中。
  • 然后就是二分图染色方案数的问题,也就是$2^{C(G)}$($C(G)$代表图连通块数)。
  • 考虑优化连边。
  • 从小到大枚举$l_i$,每个点所连的一段点在当前必定都是$r_i$连续的一段区间。
  • 增加一种$0$边,代表连的两端颜色相同。
  • 如果一个点向两边都连了$0$边,显然可以被删掉。
  • 于是连边就被优化到了$O(n)$级别,复杂度$O(n\log n)$。

代码:

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
#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 1000009
#define mod 1000000007
#define inf 0x3f3f3f3f
#define mid (l+r>>1)
using namespace std;
int n,a[N<<1],id[N<<1],L[N<<1],R[N<<1],ans=1,col[N],first[N],number;
set<int> S,T;
set<int>::iterator it;
vector<int> q;
int read()
{
char ch;
int x=1;
while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
int s=ch-'0';
while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
return s*x;
}
struct edge
{
int to,next,val;
void add(int x,int y,int z)
{
to=y,next=first[x],first[x]=number,val=z;
}
}e[N<<3];
void ins(int x,int y,int z)
{
x=id[x],y=id[y];
e[++number].add(x,y,z),e[++number].add(y,x,z);
}
void dfs(int x,int c)
{
col[x]=c;
for (int i=first[x];i;i=e[i].next)
if (col[e[i].to]==-1) dfs(e[i].to,c^e[i].val);
else
{
if (col[e[i].to]!=c^e[i].val)
{
puts("0");
exit(0);
}
}
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
{
int x=read(),y=read();
a[x]=y;
id[y]=i;
}
S.insert(-inf),S.insert(inf);
T.insert(-inf),T.insert(inf);
for (int i=1;i<=(n<<1);i++)//(i,a[i])
{
if (!a[i]) continue;
int j=a[i];
it=S.upper_bound(j);
R[j]=*it;
L[j]=*(--it);
if (L[j]>i) ins(j,L[j],1);
it=T.upper_bound(j);
it--;
for (;*it>i;it--)
{
int k=*it;
if (L[k]>i)
{
ins(k,L[k],0);
L[k]=-inf;
}
if (R[k]<j)
{
ins(k,R[k],0);
R[k]=inf;
}
if (L[k]==-inf&&R[k]==inf) q.push_back(k);
}
while ((int)q.size()>0)
{
T.erase(q.back());
q.pop_back();
}
S.insert(j),T.insert(j);
}
memset(col,-1,sizeof(col));
for (int i=1;i<=n;i++)
if (col[i]==-1)
{
ans=ans*2%mod;
dfs(i,0);
}
printf("%d\n",ans);
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#356.【JOI2017春季合宿】Port Facility

文章作者:wzf2000

发布时间:2018年03月14日 - 14:03

最后更新:2018年03月14日 - 18:03

原始链接:https://wzf2000.github.io/2018/03/14/Uoj356/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。