破解

并查集

题面

给定一个长度为$n$的数列（初始全为$0$）和$m$个区间。可不断选取区间，把该区间内的所有数$\bigotimes1$,问可得到多少不同数列。

• $30pts\ n,m\leq10$
• $60pts\ n\leq10^7,m\leq10$
• $100pts\ n,m\leq10^7$

解析

$30pts$算法

$O(2^m)$枚举是否选每个区间。

$60pts$算法

应该可以离散化，这样就有$n\leq40$。
但是屡$WA$不止是为什么。。。

sort(p+1,p+1+top);
len=unqiue(p+1,p+1+top)-p-1;
fp(i,1,n) L[i]=lower_bound(p+1,p+1+len,L[i])-p,R[i]=lower_bound(p+1,p+1+len,R[i])-p;

$100pts$算法

一个区间或者一个组合如果能被多个区间或者组合所取代（异或和相同），那么他们的本质就是一样的。
于是就成了区间覆盖问题。
然而考试时我并没有意识到这一点，于是并没有想起我的原创并查集方法。。。
于是每次将区间两端点并入同一并查集。如果两端点不在一个并查集内，就说明这区间不可被替代，它选与不选会产生不同结果，$ans*=2$。
该方法下，选取区间的顺序不影响答案。

另外，注意到$1\ 2\ $与$3\ 4\ $本质上相邻，但原$L,R$反映不出来，于是$R++$。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=5e5+100,mod=1e9+7;
struct dat{int l,r;bool operator < (const dat &o) const{return r-l<o.r-o.l;}}p[N];
int n,m,a[N],top,len,f[N*20],kuai,tot;
ll ans;
il int find(re int x){return f[x]==x?x:f[x]=find(f[x]);}
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  re int T=gi();
  while(T--)
    {
      n=gi();m=gi();tot=0;ans=1;
      fp(i,1,n+3) f[i]=i;//why?
      fp(i,1,m) p[i].l=gi(),p[i].r=gi()+1;
      fp(i,1,m)
    {
          re int fu=find(p[i].l),fv=find(p[i].r);
      if(fu^fv) f[fv]=fu,(ans*=2)%=mod;
    }
       printf("%lld\n",ans);
  }   
  return 0;
}