题意：
给出一个区间的集合，求所有集合子集中区间并的长度和；
集合大小<=100000，，答案取模1000000007；
题解：这次BC打的几乎是爆炸的。。没掉出DIV1真是万幸啊；
T1我逗比的写了一个线段树还SB的不对，发现不对劲已经半个小时了；
扔了T1搞T2还调了半天结果-5，觉得滚粗就走人啦；
言归正传，这题直接考虑显然是不行的，所以考虑离散之后统计每个小区间的贡献；
先累加每个区间覆盖次数，直接上个线段树搞；
然后统计答案需要推一下；
实际上就是 n个中取任意个，取中m个中的一个的概率是多少；
容斥一下就可以了，全部方案-不取的方案；
预处理2的幂次，然后乱搞取模啥的就可以了；
别忘了离散化之后数组大小是二倍的，所以线段树的大小也要乘2 (RE*3)；
时间复杂度O(nlogn)；
一场BC就A了一道题真是尴尬，下次一定要脑补样例再码。。
代码：
#include<stdio.h>#include<string.h>#include<algorithm>#define N 110000#define pr pair<int,int>#define lson l,mid,no<<1#define rson mid+1,r,no<<1|1#define mod 1000000007llusing namespace std;typedef long long ll;int dis[N<<1],len;pr L[N];ll sum[N<<3],cov[N<<3];ll P[N],S[N];void Pushdown(int no,int len){if(cov[no]){cov[no<<1]+=cov[no];cov[no<<1|1]+=cov[no];sum[no<<1]+=cov[no]*(len-(len>>1));sum[no<<1|1]+=cov[no]*(len>>1);cov[no]=0;}}void Pushup(int no){sum[no]=sum[no<<1]+sum[no<<1|1];}void update(int l,int r,int no,int st,int en){if(st<=l&&r<=en){cov[no]++;sum[no]+=r-l+1;}else{int mid=l+r>>1;Pushdown(no,r-l+1);if(en<=mid)update(lson,st,en);else if(st>mid) update(rson,st,en);else update(lson,st,en),update(rson,st,en);Pushup(no);}}int query(int l,int r,int no,int k){if(l==r)return sum[no];else{int mid=l+r>>1;Pushdown(no,r-l+1);if(k<=mid) return query(lson,k);elsereturn query(rson,k);}}int main(){int c,T;int n,i,l,r;scanf("%d",&T);P[1]=1;for(i=2;i<N;i++)P[i]=P[i-1]*2%mod;for(i=1;i<N;i++)S[i]=(S[i-1]+P[i])%mod;for(c=1;c<=T;c++){memset(sum,0,sizeof(sum));memset(cov,0,sizeof(cov));scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d",&L[i].first,&L[i].second);dis[i+i-1]=L[i].first;dis[i+i]=L[i].second;}sort(dis+1,dis+n+n+1);len=unique(dis+1,dis+n+n+1)-dis-1;for(i=1;i<=n;i++){l=lower_bound(dis+1,dis+len+1,L[i].first)-dis;r=lower_bound(dis+1,dis+len+1,L[i].second)-dis;if(l<=r-1)update(1,len-1,1,l,r-1);}ll ans=0;for(i=1;i<len;i++){ans=(ans+(S[n]-S[n-query(1,len-1,1,i)]+mod)%mod*(((ll)dis[i+1]-dis[i]+mod)%mod)%mod)%mod;}printf("%I64d\n",ans);}return 0;}
人生并不在于获取，更在于放得下。放下一粒种子，收获一棵大树；
