题面
众所周知，温爷家里有矿。
你可以把温爷家的矿场抽象成一条数轴。温爷家有 n 种矿，第 i 种矿可以从 [li,ri] 中的任意位置开采得到。
这个暑假， 地理老师给了温爷一个列表：温爷的暑假作业就是收集齐这些矿石。为了保证温爷的安全，温爷的爸爸选定了 m 个相对安全的采矿点，第 i 个采矿点的坐标为 ai。温爷只能选择其中一个采矿点开采他需要的矿石。
温爷是一个马虎的♂男(nv)孩子。暑假刚开始没多久，温爷就把老师的列表弄丢了。唯一的线索是，列表上的所有矿石都是温爷家有的：一共有 2n−1 种可能的列表。
温爷现在想要知道，在所有的可能的任务列表中，有多少种是他能够在某一个安全的采矿点完全收集齐的。
对于 20% 的数据，n,m≤20.
对于 40% 的数据，n≤20.
对于 60% 的数据，n,m≤1000.
对于 100% 的数据 , n,m≤1e5,1≤li,ri,ai≤1e9，保证 ai 两两不同
分析
气死我了！！！忽略了bitset的count的效率是O（N）的，以为写得满分算法，结果挂了...
将左右端点和采矿点都加进来排序离散化。
主要问题在于如何判重，我用bitset可以直接判断两个采矿点的贡献区间的交
显然的结论 ans+=2dif * (2same-1) 其中dif是两集合不重复的，same是重复的，需要用bitset的count来计算，这是60分做法
满分做法只需要每次多维护俩int，分别记录与前一个相交的数量以及现在有贡献的新区间数量。
遇到一个左端点，就使新加区间+1，遇到一个右端点，如果是在上一次标记过的，就使相交区间减一，否则使新区间数减一。
代码
60pts
#include<bits/stdc++.h> using namespace std; #define N 100010 #define ll long long #define mod 998244353 ll n,m,pl,nl,cnt,ans,tmp,flag; struct email { ll v,c,id; }a[N*4]; bitset<N>now,pre,same; bool cmp(email x,email y) { if(x.v==y.v) return x.c>y.c; return x.v<y.v; } inline void read(ll &x) { x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} } inline ll ksm(ll a,ll b) { ll ret=1; while(b) { if(b&1)ret=(ret*a)%mod; a=(a*a)%mod; b>>=1; } return ret; } int main() { read(n),read(m); for(ll i=1;i<=n;i++) { ll l,r; read(l),read(r); a[++cnt].v=l;a[cnt].c=2;a[cnt].id=i; a[++cnt].v=r;a[cnt].c=0;a[cnt].id=i; } for(ll i=1;i<=m;i++) { ll x; read(x); a[++cnt].v=x;a[cnt].c=1; } sort(a+1,a+1+cnt,cmp); ll i=1; for(ll i=1;i<=cnt;i++) { if(a[i].c==2){tmp++;now[a[i].id]=1;} if(a[i].c==0){tmp--;now[a[i].id]=0;} if(a[i].c==1) { if(flag==0) { ans=ksm(2,tmp)-1; flag=1;pre=now; } same=pre&now; if(same==now){continue;} else { pl=same.count();nl=now.count()-same.count(); ans=(ans+(ksm(2,pl)*(ksm(2,nl)-1)%mod))%mod; pre=now; } } } printf("%lld ",ans); return 0; }
100pts
#include<bits/stdc++.h> using namespace std; #define N 100010 #define ll long long #define mod 998244353 ll n,m,pl,nl,cnt,ans,tmp,flag,p,q; struct email { ll v,c,id; }a[N*4]; bitset<N>now; bool cmp(email x,email y) { if(x.v==y.v) return x.c>y.c; return x.v<y.v; } inline void read(ll &x) { x=0;char ch=getchar(); while(ch<'0'||ch>'9')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} } inline ll ksm(ll a,ll b) { ll ret=1; while(b) { if(b&1)ret=(ret*a)%mod; a=(a*a)%mod; b>>=1; } return ret; } int main() { read(n),read(m); for(ll i=1;i<=n;i++) { ll l,r; read(l),read(r); a[++cnt].v=l;a[cnt].c=2;a[cnt].id=i; a[++cnt].v=r;a[cnt].c=0;a[cnt].id=i; } for(ll i=1;i<=m;i++) { ll x; read(x); a[++cnt].v=x;a[cnt].c=1; } sort(a+1,a+1+cnt,cmp); for(int i=1;i<=cnt;i++) { if(a[i].c==2){nl++;now[a[i].id]=1;} if(a[i].c==0) { if(now[a[i].id])now[a[i].id]=0,nl--; else pl--; } if(a[i].c==1) { ans=(ans+(ksm(2,pl)*(ksm(2,nl)-1)))%mod; pl+=nl;now=0;nl=0; } } printf("%lld ",ans); return 0; }