也許更好的閱讀體驗

$\mathcal{D}escription$
給$n$對區間，要求每對區間恰好選一個使得選出來的$n$個區間有交集，問有多少方案數
$1\le n,l_i,r_i\le 5\times 10^5$

$\mathcal{S}olution$
注意到區間的值域也是$5\times 10^5$，考慮從值域入手，也就是枚舉每個點看有多少種方案使最后的交集包含這個點
設有$k$對區間的兩個區間都包含這個點，那么就有$2^k$種方案
顯然，這樣的方法會算重，因為不同的點可能對應相同的選擇方案，考慮當前枚舉的點是$i$，假設$i?1$對應的方案數為$2^m$，如果點$i$相比點$i?1$沒有新增的區間，也沒有減少區間，那么$i$和$i?1$方案數是完全一樣的，如果$i$比$i?1$新增了一些區間并沒有減少區間，那么$i$對應的方案數是包含了$i?1$對應的方案數的，新增的方案數是二者的差$2^k?2^m$，而如果減少了一些區間，那么我們記減少了后對應的方案數為$2^p$，新增的方案數仍然是二者的差$2^k?2^p$，我們只需維護這個過程即可，總復雜度$O(n)$

$\mathcal{C}ode$

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

如有哪里講得不是很明白或是有錯誤，歡迎指正
如您喜歡的話不妨點個贊收藏一下吧