# 题解 | I Non-Puzzle: Segment Pair

Non-Puzzle: Segment Pair

https://ac.nowcoder.com/acm/contest/57363/I

$\mathcal{D}escription\mathcal\left\{Description\right\}$

$nn$对区间，要求每对区间恰好选一个使得选出来的$nn$个区间有交集，问有多少方案数 $1\le n,{l}_{i},{r}_{i}\le 5×1{0}^{5}1\le n, l_i,r_i\le 5×10^5$

$\mathcal{S}olution\mathcal\left\{Solution\right\}$

$\mathcal{C}ode\mathcal\left\{Code\right\}$

#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;
}



1

07-10 23:19

23 收藏 评论