---
title: Maze
tags:
  - Connected Component
  - Segment Tree
id: "1164"
categories:
  - [OI, Data Structure]
  - [OI, Graph Theory]
date: 2017-07-12 19:50:21
---

## 题意概述

有$n$个排成一行的传送器，第$i$个传送器可以传送到$[L_i, R_i]$之间的所有传送器上（传送前的身影还在），可以多次传送。你现在随机出生在一个传送器上，求有你身影的传送器个数的期望。

## 算法分析

首先利用线段树优化建图，使得点数为$O(n)$，边数为$O(n\log n)$。

这是一张有向图。考虑在同一个强连通分量中的两个点，它们的答案一定是一样的。因此可以将图中的强连通分量缩成一个点，对每个强连通分量分别计算答案。

## 代码

```cpp
#include <cstdio>
#include <iomanip>
#include <cstring>
using namespace std;
struct node_type {
  int l, r, child[2];
} node[300001];
struct edge {
  int v, c, nxt;
} e[600001];
int n, tot, nume, id, h[300001], que[600001], dfn[300001], low[300001];
int top, sta[300001], cnt, belong[300001], pnt[300001];
long double ans;
bool vis[300001];
void add_edge(int u, int v) {
  if (u == v) return;
  e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
}
void build_tree(int root) {
  int mid = node[root].l + node[root].r >> 1;
  if (node[root].l == mid) {
    node[root].child[0] = mid, add_edge(root, mid);
  } else {
    node[++tot].l = node[root].l, node[tot].r = mid;
    node[root].child[0] = tot, add_edge(root, tot), build_tree(tot);
  }
  if (mid + 1 == node[root].r) {
    node[root].child[1] = mid + 1, add_edge(root, mid + 1);
  } else {
    node[++tot].l = mid + 1, node[tot].r = node[root].r;
    node[root].child[1] = tot, add_edge(root, tot), build_tree(tot);
  }
}
void insert_line(int root, int l, int r, int t) {
  if (node[root].l == l && node[root].r == r) {
    add_edge(t, root); return;
  }
  int mid = node[root].l + node[root].r >> 1;
  if (r <= mid) insert_line(node[root].child[0], l, r, t);
  else if (l > mid) insert_line(node[root].child[1], l, r, t);
  else {
    insert_line(node[root].child[0], l, mid, t);
    insert_line(node[root].child[1], mid + 1, r, t);
  }
}
void dfs(int t) {
  dfn[t] = low[t] = ++id;
  sta[++top] = t, vis[t] = true;
  for (int i = h[t]; i; i = e[i].nxt) {
    if (!dfn[e[i].v]) dfs(e[i].v), low[t] = min(low[t], low[e[i].v]);
    else if (vis[e[i].v]) low[t] = min(low[t], dfn[e[i].v]);
  }
  if (dfn[t] == low[t]) {
    int v; ++cnt;
    do belong[v = sta[top--]] = cnt, vis[v] = false; while (v != t);
  }
}
int bfs(int u) {
  memset(vis, false, sizeof(vis));
  int s = 0, t = 0, ret = 1;
  vis[que[++t] = u] = true;
  while (s < t) {
    int v = que[++s];
    for (int i = h[v]; i; i = e[i].nxt) {
      if (!vis[e[i].v]) {
        vis[que[++t] = e[i].v] = true;
        if (e[i].v && e[i].v <= n) ++ret;
      }
    }
  }
  return ret;
}
int main()
{
  scanf("%d", &n); tot = n + 1;
  for (int i = 1; i <= n; ++i) node[i].l = node[i].r = i;
  node[tot].l = 1, node[tot].r = n, build_tree(tot);
  for (int i = 1; i <= n; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    insert_line(n + 1, l, r, i);
  }
  for (int i = 1; i <= tot; ++i) if (!dfn[i]) dfs(i);
  for (int i = 1; i <= n; ++i) {
    if (!pnt[belong[i]]) pnt[belong[i]] = bfs(i);
    ans += pnt[belong[i]];
  }
  printf("%.6llf\n", ans / n);
  return 0;
}
```