题目链接 2017 ACM-ICPC Beijing Regional Contest Problem C
题意 给定一个$n$个点$m$条边的无向图。现在有$q$个询问，每次询问格式为$[l, r]$，即图中只有第$l$个点到第$r$个点是安全的，同时
对于某条边，如果他的两个端点都是安全的，那么这条边也是安全的。
求在该限制条件下能互相安全到达的点对数。
update：原来这个姿势叫做回滚莫队。
首先要做的就是分块，但是这道题的块的大小很难控制。
从每个点开始按度数分块，保证每个块点的度数和约等于$blocksize$。
然后就是依次处理每个块。假设当前块的左右边界分别为$l$和$r$。
首先对所有边按照左端点（这里默认左端点小于右端点）升序排序。
然后我们取出所有左端点在$[l, r]$内，右端点在$[r + 1, n]$内的询问。对这些询问按照右端点升序排序。
每次处理一个询问的时候，确保那些左右端点都落在$[r + 1, n]$的边已经被添加到并查集（这部分用双指针维护，并且不能撤销）
然后枚举那些左端点落在$[l, r]$的边，如果这条边对于当前询问来说是安全的那么添加到并查集。（这部分并查集的操作是要撤销的）
对于那些左右端点在用一个块内的询问，直接暴力合并然后恢复即可。
按照分块的策略，每个块里面左端点落在$[l, r]$的边的数量大概为$sqrt{m}$，这样乘上块的个数时间复杂度为$O(m)$
然后还要带上启发式合并的复杂度，所以总的时间复杂度为$O(m^{frac{3}{2}}logn)$
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i)
typedef long long LL;
const int N = 1e5 + 10;
struct node{
int x, y, id;
void scan(){
scanf("%d%d", &x, &y);
if (x > y) swap(x, y);
}
} e[N], q[N], tmp[N];
struct opt{
int x, y, sz, f;
LL ans;
} op[N << 1];
int T;
int cnt, now, tot, n, m, qu, bs, l, r, top, pos;
int belong[N], ed[N], in[N], sz[N], father[N];
vector <node> v[N], g[N];
LL ret[N], ans;
bool cmpx(const node &a, const node &b){ return a.x < b.x; }
bool cmpy(const node &a, const node &b){ return a.y < b.y; }
int calc(int x){
int l = 1, r = m;
if (e[1].x >= x) return 1;
if (e[m].x < x) return m + 1;
while (l + 1 < r){
int mid = (l + r) >> 1;
if (e[mid].x >= x) r = mid;
else l = mid + 1;
}
if (e[l].x >= x) return l;
else return r;
}
int getfather(int x){ return father[x] == x ? x : getfather(father[x]); }
void solve(int x, int y){
int fx = getfather(x), fy = getfather(y);
if (fx == fy) return;
if (sz[fx] < sz[fy]) swap(fx, fy);
++top;
op[top].x = fx;
op[top].y = fy;
op[top].sz = sz[fx];
op[top].f = father[fy];
op[top].ans = ans;
father[fy] = fx;
ans += 1ll * sz[fx] * sz[fy];
sz[fx] += sz[fy];
}
void undo(){
dec(i, top, 1){
int fx = op[i].x, fy = op[i].y;
father[fy] = op[i].f;
ans = op[i].ans;
sz[fx] = op[i].sz;
}
}
int main(){
scanf("%d", &T);
while (T--){
scanf("%d%d%d", &n, &m, &qu);
rep(i, 1, m) e[i].scan();
rep(i, 1, qu) q[i].scan(), q[i].id = i;
sort(e + 1, e + m + 1, cmpx);
memset(in, 0, sizeof in);
rep(i, 1, m) ++in[e[i].x];
bs = (int)floor(sqrt((double)(2 * m) * (double)(log(n) / 0.4)));
tot = 0;
now = 0;
memset(ed, 0, sizeof ed);
rep(i, 1, n){
now += in[i];
if (now >= bs){
++tot;
belong[i] = tot;
ed[tot] = i;
now = 0;
}
}
if (ed[tot] != n){
++tot;
belong[n] = tot;
ed[tot] = n;
}
dec(i, n, 1) if (!belong[i]) belong[i] = belong[i + 1];
rep(i, 1, tot){
l = ed[i - 1] + 1, r = ed[i];
v[i].clear();
g[i].clear();
rep(j, 1, m) if (e[j].x >= l && e[j].x <= r) v[i].push_back(e[j]);
rep(j, 1, qu) if (q[j].x >= l && q[j].y <= r) g[i].push_back(q[j]);
}
rep(et, 1, tot){
l = ed[et - 1] + 1, r = ed[et];
cnt = 0;
rep(i, 1, qu) if (q[i].x >= l && q[i].x <= r && q[i].y > r){
tmp[++cnt] = q[i];
}
sort(tmp + 1, tmp + cnt + 1, cmpy);
sort(e + 1, e + m + 1, cmpx);
pos = calc(r + 1);
sort(e + pos, e + m + 1, cmpy);
rep(i, 1, n) father[i] = i, sz[i] = 1;
ans = 0;
for (int j = pos, k = 1; k <= cnt; ++k){
while (e[j].y <= tmp[k].y && j <= m){
solve(e[j].x, e[j].y);
++j;
}
top = 0;
for (auto edge : v[et]){
if (tmp[k].x <= edge.x && edge.y <= tmp[k].y){
solve(edge.x, edge.y);
}
}
ret[tmp[k].id] = ans;
undo();
}
rep(i, 1, n) father[i] = i, sz[i] = 1;
ans = 0;
for (auto query : g[et]){
top = 0;
for (auto edge : v[et]){
if (query.x <= edge.x && edge.y <= query.y){
solve(edge.x, edge.y);
}
}
ret[query.id] = ans;
undo();
}
}
rep(i, 1, qu) printf("%lld
", ret[i]);
}
return 0;
}