由于懒癌，好久以前就从洛咕日报上有这么个科技了，但是现在才学。
有一种题目就是限制我们边权只能走<=x或>=x的，这种题目显然我们可以离线+kruskal维护，但是他强制在线就有点蛋疼了，这时我们可以用一棵二叉树记录kruskal的合并顺序，在树上搞搞倍增什么的做到在线处理。
具体地说，我们在kruskal合并连通块时，新建一个节点，将当前枚举边的边权赋予这个节点，让这个节点成为这两个连通块代表节点的父亲，并让这个节点成为新连通块的代表节点。
显然，我们最后形成了一棵满足二叉堆性质的树。我们在树上瞎搞搞就可以在线处理。
例如，我们要查询无向图中从某个点p开始经过<=x的边能到达点的数量。我们建立大根Kruskal重构树，维护倍增信息，我们在树上倍增跳p的父亲，直到跳到<=x的最大的点为止，这个子树中叶子节点的数量即为答案。
例题：[NOI2018]归程
做了这题后发现非常水。题目大意就是每次询问从一个节点v开始走，经过边的海拔>p能走到所有点中，距离1号点的距离中最短的是什么。我们先从1号节点跑一遍dij求出所有最短路，然后建立小根Kruskal重构树，对于每个点维护子树中到1号点距离最短的点的距离。在Kruskal树上倍增条到海拔>p的深度最小的那个点，输出那个点存储的最短距离即可。
代码写的不算太丑，就放上来吧。（其实也挺丑的）
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v, w, ne;
} a[4000010];
struct fuck
{
int u, v, a;
} e[2000010];
int h[2000010], tmp;
int dis[4000010], ds[4000010], fa[4000010][23], val[4000010];
bool v[2000010];
int n, m;
void add(int x, int y, int z)
{
a[++tmp] = (edge){y, z, h[x]};
h[x] = tmp;
}
bool operator>(const fuck &x, const fuck &y)
{
return x.a > y.a;
}
int getf(int x)
{
return ds[x] == x ? x : ds[x] = getf(ds[x]);
}
void work()
{
scanf("%d%d", &n, &m);
tmp = 0;
for (int i = 1; i <= n; i++)
h[i] = 0, dis[i] = val[i] = 0x3f3f3f3f, v[i] = false, ds[i] = i, fa[i][0] = 0;
for (int t, i = 1; i <= m; i++)
{
scanf("%d%d%d%d", &e[i].u, &e[i].v, &t, &e[i].a);
add(e[i].u, e[i].v, t), add(e[i].v, e[i].u, t);
}
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que;
que.push(make_pair(0, 1));
dis[1] = 0;
while (!que.empty())
{
int x = que.top().second;
que.pop();
if (v[x] == true)
continue;
v[x] = true;
for (int i = h[x]; i != 0; i = a[i].ne)
if (v[a[i].v] == false && dis[x] + a[i].w < dis[a[i].v])
dis[a[i].v] = dis[x] + a[i].w, que.push(make_pair(dis[a[i].v], a[i].v));
}
sort(e + 1, e + 1 + m, greater<fuck>());
int tot = n;
for (int i = 1; i <= m; i++)
{
int f1 = getf(e[i].u), f2 = getf(e[i].v);
if (f1 != f2)
{
int p = ++tot;
ds[p] = p;
fa[p][0] = 0;
val[p] = e[i].a;
dis[p] = min(dis[f1], dis[f2]);
ds[f1] = p;
ds[f2] = p;
fa[f1][0] = p;
fa[f2][0] = p;
}
}
for (int j = 1; j <= 19; j++)
for (int i = 1; i <= tot; i++)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
int q, k, s, lastans = 0;
val[0] = -2333;
scanf("%d%d%d", &q, &k, &s);
for (int v, p, i = 1; i <= q; i++)
{
scanf("%d%d", &v, &p);
v = (v + k * lastans - 1) % n + 1;
p = (p + k * lastans) % (s + 1);
for (int i = 19; i >= 0; i--)
if (val[fa[v][i]] > p)
v = fa[v][i];
printf("%d
", lastans = dis[v]);
}
}
int main()
{
int t;
scanf("%d", &t);
while (t --> 0)
{
work();
}
return 0;
}
还有一道题是BZOJ3545 Peaks，要用Kruskal重构树+主席树合并维护
代码还没写呢，该好好复习一遍主席树去了。