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 |
|