Segment Tree Offline

vector<Object> tree[N << 2];  // 线段树

void update(int ql, int qr, Object obj, int i, int l, int r) {  // 插入
  if (ql <= l && r <= qr) {
    tree[i].push_back(obj);
    return;
  }
  if (ql <= mid) update(ql, qr, obj, ls, l, mid);
  if (qr > mid) update(ql, qr, obj, rs, mid + 1, r);
}

stack<Object> sta;  // 用于撤销的栈
Object now;         // 当前的信息并
Object ans[N];      // 答案

void solve(int i, int l, int r) {
  auto lvl = sta.size();  // 记录一下应当撤销到第几个
  for (Object x : tree[i]) sta.push(now), now = Merge(now, x);  // 合并信息
  if (l == r)
    ans[i] = now;  // 记录一下答案
  else
    solve(ls, l, mid), solve(rs, mid + 1, r);  // 分治
  while (sta.size() != lvl) {                  // 撤销信息
    now = sta.top();
    sta.pop();
  }
}
```

对于每一个时刻，若此时该图为二分图，输出 `Yes`，否则输出 `No`．

??? note "解题思路"
    使用种类并查集来维护一个图是否是二分图，然后就可以套用线段树分治了．
    
    注意可撤销的并查集不能路径压缩，只能按秩合并．

??? note "参考代码"
    ```cpp
    --8<-- "docs/topic/code/segment-tree-offline/segment-tree-offline_1.cpp"
    ```

对于每种颜色，请判断假如删去所有这种颜色的边，得到的图是否连通？是否是一棵树？

输出满足删去后图连通的颜色数和删去后图是树的颜色数．

??? note "解题思路"
    对于每一种颜色，建立一个时间，在这个时间内没有这个颜色的边，其他边都有．用一个并查集维护一下即可．

??? note "参考代码"
    ```cpp
    --8<-- "docs/topic/code/segment-tree-offline/segment-tree-offline_2.cpp"
    ```

有 $q$ 个操作，支持：

-   `A x y` 连边 $(x,y)$．
-   `Q x y` 输出经过边 $(x,y)$ 的路径数．

允许离线．

??? note "解题思路"
    考虑允许离线，因此可以想到线段树分治．
    
    然后考虑如何支持 Q 操作．如果不存在 $(x,y)$ 这条边，答案就是 $x$ 所在连通块大小乘上 $y$ 所在连通块大小．可以用并查集维护．
    
    因此你可以将 Q 拆成三个时间 $k-1,k,k+1$．其中 $k-1$ 是这条边的终止时刻，$k+1$ 是这条边的起始时刻．这样 $k$ 就没有这条边，正好回答询问．

??? note "参考代码"
    ```cpp
    --8<-- "docs/topic/code/segment-tree-offline/segment-tree-offline_3.cpp"
    ```

-   `C x` 将第 $x$ 个点的颜色反转．
-   `G` 询问树上两个黑色点的最远距离．特别地，若不存在黑色点，输出 $-1$．

允许离线．

??? note "解题思路"
    首先考虑如何维护树上点集的直径，有下面的推论：
    
    > 对于一个集合 $S$ 和只有一个点的集合 $\{P\}$．若集合 $S$ 的直径为 $(U,V)$．则点集 $S\cap\{P\}$ 的直径只可能为 $(U,V),(U,P)$ 或 $(V,P)$．
    
    然后考虑解决原问题．我们可以考虑维护黑色点集，维护每一个点在黑色点集中的若干个时间段（具体你开一个桶记录一下上一次进入黑色点集的时刻即可）．
    
    然后就自然地想到离线，将所有时间刻插入到线段树中．然后在线段树上分治，每次线段树上的点会记录当前时间段点集新增的点，新增点可以使用上面的推论，找到新点集直径的两个端点．
    
    撤销是平凡的，开一个栈记录一下直径端点的变化即可．

??? note "参考代码"
    ```cpp
    --8<-- "docs/topic/code/segment-tree-offline/segment-tree-offline_4.cpp"
    ```