# 2. 题解

Emmm。。。

Woc。。。我还是跳楼自杀吧。。。

• 最短路求出每个点到 1 号点的最短距离
• 把询问从大到小排序
• 从大到小加边，并查集维护每个联通快内的点到 1 号点的距离中的最小值
• 对于一个询问，如果所有海拔大于它的边都加上了就直接查询问中的点所在的联通块内到点 1 的最小距离，输出即可。

#include <bits/stdc++.h>

#define NS (200005)
#define MS (400005)
#define FIR first
#define SEC second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

template <typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

struct graph
{
int head[NS], to[MS << 1], nxt[MS << 1], w[MS << 1], sz;
graph() {init();}
void push(int a, int b, int c)
{
nxt[sz] = head[a], to[sz] = b, w[sz] = c, head[a] = sz++;
}
} g;

struct edge
{
int u, v, l, a;
edge() {u = v = l = a = 0;}
edge(int x, int y, int p, int q)
{
u = x, v = y, l = p, a = q;
}
bool operator > (const edge oth) const
{
if (a == oth.a)
{
if (l == oth.l)
{
if (u == oth.u) return v > oth.v;
return u > oth.u;
}
return l > oth.l;
}
return a > oth.a;
}
} E[MS];

int T, n, m, h[MS], dis[NS], He[NS];

priority_queue<PII, vector<PII>, greater<PII> > pq;

void dij()
{
memset(dis, 127, sizeof(dis)), pq.push(PII(0, 1)); PII F;
while (!pq.empty())
{
F = pq.top(), pq.pop();
if (F.FIR >= dis[F.SEC]) continue;
dis[F.SEC] = F.FIR;
for (int i = g.head[F.SEC]; ~i; i = g.nxt[i])
if (dis[g[i]] > dis[F.SEC] + g.w[i])
pq.push(PII(dis[F.SEC] + g.w[i], g[i]));
}
}

/**CMT**/

struct N {int x, y, l, r;} e[19000005];

int root[MS], sz;

void Build(int l, int r, int& a)
{
a = sz++;
if (l == r) {e[a].x = l, e[a].y = dis[l], e[a].l = e[a].r = 0; return;}
int mid = (l + r) >> 1;
Build(l, mid, e[a].l), Build(mid + 1, r, e[a].r);
}

PII Query(int x, int a)
{
int L = 1, R = n, Mid;
while (L < R)
{
Mid = (L + R) >> 1;
if (x <= Mid) a = e[a].l, R = Mid;
else a = e[a].r, L = Mid + 1;
}
return PII(e[a].x, e[a].y);
}

void Updatex(int x, int d, int L, int R, int& p, int q)
{
p = sz++, e[p] = e[q];
if (L == R) {e[p].x = d; return;}
int Mid = (L + R) >> 1;
if (x <= Mid) Updatex(x, d, L, Mid, e[p].l, e[q].l);
else Updatex(x, d, Mid + 1, R, e[p].r, e[q].r);
}

void Updatey(int x, int d, int L, int R, int& p, int q)
{
p = sz++, e[p] = e[q];
if (L == R) {e[p].y = d; return;}
int Mid = (L + R) >> 1;
if (x <= Mid) Updatey(x, d, L, Mid, e[p].l, e[q].l);
else Updatey(x, d, Mid + 1, R, e[p].r, e[q].r);
}

/**CMT**/

PII findf(int a, int h)
{
PII tmp = Query(a, root[h]);
if (tmp.FIR == a) return tmp;
return findf(tmp.FIR, h);
}

int main(int argc, char const* argv[])
{
IN(T);
while (T--)
{
IN(n), IN(m), g.init(), sz = 0;
for (int i = 1; i <= n; i += 1) He[i] = 1;
for (int i = 1, u, v, a, b; i <= m; i += 1)
{
IN(u), IN(v), IN(a), IN(b);
E[i] = edge(u, v, a, b), g.push(u, v, a), g.push(v, u, a);
}
sort(E + 1, E + 1 + m, greater<edge>());
for (int i = 1; i <= m; i += 1) h[i] = E[i].a;
dij(), Build(1, n, root[0]); PII r1, r2;
for (int i = 1; i <= m; i += 1)
{
root[i] = root[i - 1];
r1 = findf(E[i].u, i - 1), r2 = findf(E[i].v, i - 1);
if (r1.FIR != r2.FIR)
{
if (He[r1.FIR] > He[r2.FIR]) swap(r1, r2);
else if (He[r1.FIR] == He[r2.FIR]) He[r2.FIR]++;
Updatex(r1.FIR, r2.FIR, 1, n, root[i], root[i]);
Updatey(r2.FIR, min(r1.SEC, r2.SEC), 1, n, root[i], root[i]);
}
}
int q, k, s, lst = 0;
IN(q), IN(k), IN(s);
for (int C = 1, v, p; C <= q; C += 1)
{
IN(v), IN(p);
v = ((LL)v + k * lst - 1) % n + 1;
p = ((LL)p + k * lst) % (s + 1);
p = lower_bound(h + 1, h + 1 + m, p, greater<int>()) - h - 1;
r1 = findf(v, p), lst = r1.SEC, printf("%d\n", lst);
}
}
return 0;
}


### 4 条评论

#### foreverpiano · 2018年7月19日 9:49 下午

kruscal 重构树也可以做还更好写 qwq

#### XZYQvQ · 2018年7月19日 10:44 下午

emmmm Yes I know…
克鲁斯卡尔重构树就做过一题，忘得一干二净.png
跑得应该比可持久化要快吧 QvQ
（emmm 又发了一遍提醒邮件 QvQ 大佬别打我我只是在测试而已。。。感觉 QQ 的那个 foxmail 挺不错的样子试试看嘿嘿嘿）

qwq

#### boshi · 2018年7月20日 9:25 下午

我试了一下快 30% 到 40%