目录
显示
题目链接
题解
Subtask 2
容易发现，当 \(A_i \lt A_j \lt B_i \lt B_j\) 时，\(i,j\) 不能安排在同一个栈中。
如果在两个不能放在同一个栈的元素间连一条边，容易发现这是一个二分图染色的模型。
设最后形成了 \(x\) 个连通分量，因为每个连通分量都有两种染色方案，所以总方案数为 \(2^x\)。
当然，如果有一个连通分量不是二分图，则染色无法进行，答案就是零。
暴力枚举点对连边可以做到 \(O(n^2)\) 的时间复杂度，从而得到 \(22\) 分。
Subtask 4
上面做法的瓶颈在于连的边太多了。我们需要降低边的规模。
先将所有区间按左端点升序排序，然后按右端点从小到大的顺序考虑每一个元素。
容易发现每个元素能连的边，在数组里是一个连续的区间。
我们设第一次连边的范围是 \([l_1,r_1]\)，第二次连边的范围是 \([l_2,r_2]\)。
如果这两个范围有重叠部分，则重复向重叠部分连边可能会形成偶环。偶环是不影响结果的，所以第一次连边结束后，第二次连边只需向重叠部分的其中一个点连边即可。
详细来说，设 \(nxt_i\) 表示连完这个点后下一个要连的点。
以上面为例，第一次连边结束后，第一次连的边的 \(nxt\) 指针都会指向 \(r_1\) 后面的那个元素。
可以证明，这样做的时间复杂度为 \(O(n \log n)\)，可以通过本题。
#include <cstring>
#include <iostream>
#include <vector>
#define MOD 1000000007
using namespace std;
int p[2000005],vis[1000005],col[1000005];
vector<int> e[1000005];
int fa[2000005],nxt[1000005];
int cnt;
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool dfs(int u,int c)
{
col[u]=c;
for(auto v:e[u])
if(col[v]==col[u])return false;
else if(col[v]==-1)
{
if(!dfs(v,c^1))return false;
}
return true;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int l,r;
cin>>l>>r;
p[l]=p[r]=i;
}
for(int i=1;i<=n+1;i++)
fa[i]=i,nxt[i]=i;
for(int i=1;i<=2*n;i++)
if(!vis[p[i]])
vis[p[i]]=++cnt;
else
{
int id=vis[p[i]],t;
fa[id]=find(id+1);
for(int j=fa[id];j<=cnt;j=t)
{
e[id].push_back(j);
e[j].push_back(id);
t=find(nxt[j]+1);
nxt[j]=cnt;
}
}
memset(col,-1,sizeof(col));
int ans=1;
for(int i=1;i<=n;i++)
if(col[i]==-1)
{
if(dfs(i,0))ans=ans*2%MOD;
else ans=0;
}
cout<<ans<<endl;
return 0;
}