JZOJ5146:港湾

Description

放假啦！
小林和康娜来到了港口，看到有货船正在卸货。
港口十分狭窄，只有两个卸货区可以使用。每个卸货区上面可以堆积任意多个箱子。
每卸下来一个箱子，工作人员都会把这个箱子放在某个卸货区的顶端。之后，当车辆来运走这个箱子的时候，也必须保证这个箱子在某个卸货区的顶端。
港口今天一共运来了N个箱子，第i个箱子在时刻Ai被卸货，在时刻Bi被取走。康娜发现，每个箱子被取走时，都恰好位于所在卸货区的顶端。
康娜觉得很有意思，她想要知道，有多少种卸货方案，使得每个箱子在被取走时都位于所在卸货区的顶端呢？
两种方案不同，当且仅当存在一个箱子，使得在两个方案中这个箱子被放在了不同的卸货区。

Input

第一行一个正整数N，表示箱子的数量。
接下来N行，每行两个空格分割的正整数Ai和Bi，表示第i个箱子在时刻Ai被卸货，在时刻Bi被取走。

Output

输出一行一个非负整数，表示合法的卸货方案。由于这个数字可能过大，你只需要输出方案数对1,000,000,007的模数即可。

Sample Input

1 3

2 5

4 8

6 7

Sample Output

HINT

对于10%的数据，N<=20
对于30%的数据，N<=2000
对于100%的数据，
1<=N<=10^5
1<=Ai<Bi<=2N
A1,A2,...,AN,B1,B2,...,BN构成1...2N的一个排列。

题解：

如果两个物品i,j不能放在一个卸货区上（即 a[i]<a[j]<b[i]<b[j] or a[j]<a[i]<b[j]<b[i]），则记为i与j冲突，在i与j之间连一条边。

这样建出了一个无向图，若其能二分图染色，则存在方案，为2^(连通块个数)。

如果暴力建图，则复杂度为O(n^2)，不可行。

考虑用带权并查集，每个点支持查询祖先以及其与祖先染色是否相同，就可以维护连通块了。

现在的问题是如何去掉重复意义的边。

我们可以用线段树套vector来维护右端点在[l,r]之间的物品。这些物品代表的是其所属的并查集以及其在并查集中的染色。若某个vector中的两个物品代表的意义相同，则可以只留一个。

我们把物品按照左端点排序，按顺序插入线段树，则前i-1个物品中，右端点在[a[i]+1,b[i]-1]的物品都与物品i冲突。

这些物品可以在线段树区间[a[i]+1,b[i]-1]中查询得到。我们把这些物品以及物品i所代表的并查集合在一起。

若有两个物品代表的并查集相同，但是染色不同，则发生冲突，不可二分图染色，输出0。

然后，我们清空区间[a[i]+1,b[i]-1]所用到的线段树节点的vector（这些物品现在都代表同一个并查集），根据清空前其中的物品代表的染色，最多重新放入两个。

最后，我们在包含b[i]的线段树节点的vector中放入物品i。

最后，输出ans=2^(并查集个数)。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 vector <int> v[];

 int t[][],n,fa[][],bo[][],cnt,nn,tot,now;

 pair <int,int> a[],b[];

 void build(int l,int r,int fa)

 {

     cnt++; int x=cnt; t[x][]=l; t[x][]=r;

     if(t[x][]==t[fa][])t[fa][]=x;else t[fa][]=x;

     if(l==r)return;

     build(l,(l+r)/,x); build((l+r)/+,r,x);

 }

 int get2(int x);

 int get1(int x)

 {

     if(fa[x][]!=x){ int a=fa[x][]; fa[x][]=get1(a); fa[x][]^=get2(a); }

     return fa[x][];

 }

 int get2(int x)

 {

     if(fa[x][]!=x){ int a=fa[x][]; fa[x][]=get1(a); fa[x][]^=get2(a); }

     return fa[x][];

 }

 void ss(int x,int l,int r)

 {

     if(l>r)return;

     int ll=t[x][],rr=t[x][]; int mid=(ll+rr)/;

     if((ll==l)and(rr==r))

     {

         int mm=v[x].size();

         for(int i=;i<mm;i++)

         {

             int aa=get1(v[x][i]),bb=get2(v[x][i]); int xxx=v[x][i];

             if(bo[aa][bb]==){ bo[aa][bb]=; nn++; b[nn]=make_pair(aa,bb); }

         }

         return;

     }

     if(r<=mid)ss(t[x][],l,r);else

     if(l>mid)ss(t[x][],l,r);else

     { ss(t[x][],l,mid); ss(t[x][],mid+,r); }

 }

 void ss2(int x,int l,int r)

 {

     if(l>r)return;

     int ll=t[x][],rr=t[x][]; int mid=(ll+rr)/;

     if((ll==l)and(rr==r))

     {

         int mm=v[x].size(),q[]; q[]=; q[]=;

         for(int i=;i<mm;i++)

         {

             int bb=get2(v[x][i]);

             if(q[bb]==)q[bb]=v[x][i];

         }

         v[x].clear();

         if(q[]>)v[x].push_back(q[]);

         if(q[]>)v[x].push_back(q[]);

         return;

     }

     if(r<=mid)ss2(t[x][],l,r);else

     if(l>mid)ss2(t[x][],l,r);else

     { ss2(t[x][],l,mid); ss2(t[x][],mid+,r); }

 }

 void ss3(int x,int l,int y)

 {

     int ll=t[x][],rr=t[x][]; int mid=(ll+rr)/;

     v[x].push_back(y); if(ll==rr)return;

     if(l<=mid)ss3(t[x][],l,y);

     if(l>mid)ss3(t[x][],l,y);

 }

 void hb(int x,int y,int z)

 {

     int a=get1(x); if(a==y)return;

     fa[a][]=y; fa[a][]^=z; tot--;

 }

 int main()

 {

     freopen("port.in","r",stdin);

     freopen("port.out","w",stdout);

     scanf("%d",&n); tot=n;

     for(int i=;i<=n;i++)scanf("%d%d",&a[i].first,&a[i].second),fa[i][]=i;

     sort(a+,a+n+); build(,*n,);

     for(int i=;i<=n;i++)

     {

         nn=; now=i;

         ss(,a[i].first+,a[i].second-);

         sort(b+,b+nn+);

         for(int j=;j<=nn;j++)

         {

             if((j>)and(b[j].first==b[j-].first)){ printf("0\n"); return ; }

             hb(b[j].first,i,b[j].second^); bo[b[j].first][b[j].second]=;

         }

         ss2(,a[i].first+,a[i].second-);

         ss3(,a[i].second,i);

     }

     long long ans=;

     for(int i=;i<=tot;i++)ans=(ans*)%;

     printf("%lld\n",ans);

 }

巴特西