[关闭]
@ysner 2018-07-19T11:08:55.000000Z 字数 1463 阅读 2149

破解

并查集


题面

给定一个长度为的数列(初始全为)和个区间。可不断选取区间,把该区间内的所有数,问可得到多少不同数列。

解析

算法

枚举是否选每个区间。

算法

应该可以离散化,这样就有
但是屡不止是为什么。。。

  1. sort(p+1,p+1+top);
  2. len=unqiue(p+1,p+1+top)-p-1;
  3. 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;

算法

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

另外,注意到本质上相邻,但原反映不出来,于是

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<map>
  8. #define re register
  9. #define il inline
  10. #define ll long long
  11. #define max(a,b) ((a)>(b)?(a):(b))
  12. #define min(a,b) ((a)<(b)?(a):(b))
  13. #define fp(i,a,b) for(re int i=a;i<=b;i++)
  14. #define fq(i,a,b) for(re int i=a;i>=b;i--)
  15. using namespace std;
  16. const int N=5e5+100,mod=1e9+7;
  17. struct dat{int l,r;bool operator < (const dat &o) const{return r-l<o.r-o.l;}}p[N];
  18. int n,m,a[N],top,len,f[N*20],kuai,tot;
  19. ll ans;
  20. il int find(re int x){return f[x]==x?x:f[x]=find(f[x]);}
  21. il ll gi()
  22. {
  23. re ll x=0,t=1;
  24. re char ch=getchar();
  25. while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  26. if(ch=='-') t=-1,ch=getchar();
  27. while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  28. return x*t;
  29. }
  30. int main()
  31. {
  32. re int T=gi();
  33. while(T--)
  34. {
  35. n=gi();m=gi();tot=0;ans=1;
  36. fp(i,1,n+3) f[i]=i;//why?
  37. fp(i,1,m) p[i].l=gi(),p[i].r=gi()+1;
  38. fp(i,1,m)
  39. {
  40. re int fu=find(p[i].l),fv=find(p[i].r);
  41. if(fu^fv) f[fv]=fu,(ans*=2)%=mod;
  42. }
  43. printf("%lld\n",ans);
  44. }
  45. return 0;
  46. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注