题解：P10365 [PA2024] Kraniki
小超手123
·
·
题解
分析：
记 cnt_{i} 表示能到达 i 的平台的个数（包括本身），那么答案显然为 \sum_{i=1}^{n} \frac{1}{cnt_{i}}。因为 cnt_{i} 个数随意排列，i 在最后一个位置的概率为 \frac{cnt_{i}}{1}。
考虑计算 cnt：对于平台 u 而言，高度从低往高更新，如果 v 与 u 有交且不是 v 包含 u，那么 u \leftarrow u \cup v。最后 cnt 就是被 u 覆盖的区间。
记 L2_{i},R2_{i} 分别表示覆盖 i 的左右端点的在 i 平台上面的高度最低的平台。
如何找天花板呢？记 L1_{i},R1_{i} 分别表示 i 平台的左右端点能覆盖到的在 i 下面高度最高的平台。
再记一个 Go_{i} 表示 i 能跳到最高的平台，那么 i 从大到小枚举，Go_{L1_{i}} \leftarrow Go_{i},Go_{R1_{i}} \leftarrow Go_{i}。
知道了平台的高度就可以很套路地使用倍增计算这个图形所围成的平台的个数。
时间复杂度 $O(n \log n)$。
##### 代码：
```cpp
#include<bits/stdc++.h>
#define int long long
#define N 1000005
#define mod 1000000007
using namespace std;
int n;
int Pow(int a, int n) {
if(n == 0) return 1;
if(n == 1) return a;
int x = Pow(a, n / 2);
if(n % 2 == 0) return x * x % mod;
else return x * x % mod * a % mod;
}
int inv(int x) {
return Pow(x, mod - 2);
}
int c[N * 4], tag[N * 4];
void maketag(int u, int x) {
c[u] = x;
tag[u] = x;
}
void pushdown(int u) {
if(!tag[u]) return;
maketag(u * 2, tag[u]);
maketag(u * 2 + 1, tag[u]);
tag[u] = 0;
}
void update(int u, int L, int R, int l, int r, int x) {
if(R < l || r < L) return;
if(l <= L && R <= r) {
maketag(u, x);
return;
}
int mid = (L + R) / 2;
pushdown(u);
update(u * 2, L, mid, l, r, x);
update(u * 2 + 1, mid + 1, R, l, r, x);
}
int query(int u, int L, int R, int x) {
if(L == R) return c[u];
int mid = (L + R) / 2;
pushdown(u);
if(x <= mid) return query(u * 2, L, mid, x);
else return query(u * 2 + 1, mid + 1, R, x);
}
int t[N];
int lowbit(int x) {
return x & (-x);
}
void add(int x, int y) {
for(int i = x; i <= 2 * n; i += lowbit(i))
t[i] += y;
}
int query(int x) {
int res = 0;
for(int i = x; i; i -= lowbit(i))
res += t[i];
return res;
}
int ask(int L, int R) {
if(L > R) return 0;
return query(R) - query(L - 1);
}
int ans, l[N], r[N], Go[N]; //Go[i]表示i最高跳到的平台
int L1[N], R1[N]; //表示i能直接流到的高度最大的平台
int L2[N], R2[N]; //表示i头上与它有交集的高度最低的平台
int L[N][22], R[N][22], SL[N][22], SR[N][22];
struct node {
int ll, rr, h;
}a[N];
bool cmp(node x, node y) {
return x.rr < y.rr;
}
bool cmp2(node x, node y) {
return x.ll < y.ll;
}
void init() {
for(int i = 1; i <= n; i++) {
L1[i] = query(1, 1, 2 * n, l[i]);
R1[i] = query(1, 1, 2 * n, r[i]);
update(1, 1, 2 * n, l[i], r[i], i);
}
for(int i = n; i >= 1; i--) {
Go[L1[i]] = max(Go[L1[i]], Go[i]);
Go[R1[i]] = max(Go[R1[i]], Go[i]);
}
update(1, 1, 2 * n, 1, 2 * n, n + 1);
for(int i = n; i >= 1; i--) {
L[i][0] = L2[i] = query(1, 1, 2 * n, l[i]);
R[i][0] = R2[i] = query(1, 1, 2 * n, r[i]);
update(1, 1, 2 * n, l[i], r[i], i);
//cout << i << " : " << L[i][0] << " , " << R[i][0] << endl;
}
sort(a + 1, a + n + 1, cmp);
for(int i = 1; i <= n; i++) {
//cout << a[i].h << endl;
add(a[i].h, 1);
SR[a[i].h][0] = ask(a[i].h, R[a[i].h][0]);
}
sort(a + 1, a + n + 1, cmp2);
memset(t, 0, sizeof(t));
for(int i = 1; i <= n; i++) {
add(a[i].h, 1);
SL[a[i].h][0] = ask(a[i].h + 1, L[a[i].h][0] - 1);
}
//for(int i = 1; i <= n; i++) cout << i << " : " << SL[i][0] << endl;
}
signed main() {
//freopen("ex_water3.in", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
Go[i] = i;
a[i].ll = l[i];
a[i].rr = r[i];
a[i].h = i;
}
init();
for(int j = 1; j <= 20; j++) {
for(int i = 1; i <= n; i++) {
L[i][j] = L[L[i][j - 1]][j - 1];
R[i][j] = R[R[i][j - 1]][j - 1];
SL[i][j] = SL[i][j - 1] + SL[L[i][j - 1]][j - 1];
SR[i][j] = SR[i][j - 1] + SR[R[i][j - 1]][j - 1];
}
}
for(int i = 1; i <= n; i++) {
int cnt = 0, x = i;
for(int dep = 20; dep >= 0; dep--) {
if(R[x][dep] != 0 && R[x][dep] <= L[Go[i]][0]) {
cnt += SR[x][dep];
x = R[x][dep];
}
}
x = i;
for(int dep = 20; dep >= 0; dep--) {
if(L[x][dep] != 0 && L[x][dep] <= L[Go[i]][0]) {
cnt -= SL[x][dep];
x = L[x][dep];
}
}
ans = (ans + inv(cnt)) % mod;
}
cout << ans;
return 0;
}
/*
5
2 9
3 4
1 8
6 10
5 7
*/
```