小分分
本题要求所有好点的覆盖情况之和，已知好点的范围是1~5e5，从题上而言直接开一个5e5+1的数组来记录每一次之后的情况，然后对每一个数的情况进行相加即可。
但由于这样做就将复杂度提升到了O(n^2) ，一定会超时。在这时候可以想到由于是区间性的东西，可以使用差分与前缀和来对区间进行批量处理。d[i][j]是用来记录三种状态中每个数每种状态各是多少的，其中i表示三种状态，j表示0~5e5中状态对应的个数。之后通过得到的当前数有几种0态，几种1态，几种2态就可以得到最后的结果。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5;
const int p = 1e9+7;
vector<vector<int>> d(3, vector<int>(maxn + 1));
int main() {
vector<int> pw(maxn+1);
pw[0] = 1;
for (int i=1;i<=maxn;i++) {
pw[i] = pw[i-1]*2LL%p;
}
int n;
int l1, r1, l2, r2;
scanf("%d", &n);
while (n--) {
vector<array<int, 2> > va;
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
va.push_back({l1, 1});
va.push_back({r1+1, -1});
va.push_back({l2, 1});
va.push_back({r2+1, -1});
sort(va.begin(), va.end());
int val=0, lst=0;
for (auto[x,y] : va) {
if (lst<x) {
d[val][lst]++;
d[val][x]--;
}
val += y; lst = x;
}
d[0][lst]++;
}
//计算前缀和
for (int i=0;i<=2;i++) {
for (int j=1;j<=maxn;j++) {
d[i][j] += d[i][j-1];
}
}
long long ans = 0;
for (int i=1;i<=maxn;i++) {
if (d[0][i]==0) ans = (ans + pw[d[2][i]])%p;
}
cout<<ans;
return 0;
}
查看7道真题和解析