区间交

题目链接

Problem

选取一些区间，使其区间交不小于\(k\)。 # Solution 区间交即是选出的区间的\([L-max,R-min]\)。将所有区间按左端点排序，枚举每一个区间(区间的\(r-l >= k\))将其左端点作为\(L-max\)。设之前右端点不小于\(L-max+k\)的区间有\(a\)个，对答案的贡献是\(2^a\)。可以用数据结构(比如支持单点修改和区间查询的线段树)或者优先队列维护。 # Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int MOD=1e9+7;
int n,k,ans;
priority-queue<int, vector<int>, greater<int> > q;
struct node {
	int l,r;
	inline bool operator < (const node &b) const {
		return l<b.l;
	}
}a[N];
long long qpow(int a,int b) {
	if(b==0) return 1;
	if(b&1) return (qpow(a,b-1)*a)%MOD;
    long long mul=qpow(a,b>>1);
    return (mul*mul)%MOD;
}
int main() {
	scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) 
    	scanf("%d%d",&a[i].l,&a[i].r);
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) {
    	while(!q.empty()&&q.top()<a[i].l+k) q.pop();
    	if(a[i].l+k<=a[i].r) ans=(ans+(qpow(2,q.size())))%MOD;
    	q.push(a[i].r);
    }
    printf("%d\n",ans%MOD);
    return 0;
}