给对区间，要求每对区间恰好选一个使得选出来的
个区间有交集，问有多少方案数
注意到区间的值域也是，考虑从值域入手，也就是枚举每个点看有多少种方案使最后的交集包含这个点
设有对区间的两个区间都包含这个点，那么就有
种方案
显然，这样的方法会算重，因为不同的点可能对应相同的选择方案，考虑当前枚举的点是，假设
对应的方案数为
，如果点
相比点
没有新增的区间，也没有减少区间，那么
和
方案数是完全一样的，如果
比
新增了一些区间并没有减少区间，那么
对应的方案数是包含了
对应的方案数的，新增的方案数是二者的差
，而如果减少了一些区间，那么我们记减少了后对应的方案数为
，新增的方案数仍然是二者的差
，我们只需维护这个过程即可，总复杂度
#include <cstdio>
#include <vector>
using namespace std;
const int maxn = 5e5 + 10;
const int mod = 1e9 + 7;
int n, k, ans;
int num[maxn], mi[maxn];
vector <int> in[maxn], out[maxn];
int mo (int x)
{
if (x >= mod) return x - mod;
return x;
}
int main ()
{
scanf("%d", &n);
mi[0] = 1;
for (int i = 1; i <= n; ++i) mi[i] = mo(mi[i - 1] << 1);
for (int i = 1, l, r; i <= n; ++i) {
scanf("%d%d", &l, &r);
in[l].push_back(i), out[r + 1].push_back(i);
scanf("%d%d", &l, &r);
in[l].push_back(i), out[r + 1].push_back(i);
}
int tot = 0, mx = 500000, lst = mx + 1;
for (int i = 1; i <= mx; ++i) {
for (int v : out[i]) {
if (num[v] == 2) --k;
--num[v];
if (!num[v]) --tot;
}
if (tot < n) lst = mx + 1;
else lst = k;
for (int v : in[i]) {
if (!num[v]) ++tot;
++num[v];
if (num[v] == 2) ++k;
if (tot == n) {
if(lst == mx + 1 || k > lst) ans = mo(mo(ans + mod - mi[lst]) + mi[k]);
lst = k;
}
}
}
printf("%d\n", ans);
return 0;
}如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧