本文共 4069 字，大约阅读时间需要 13 分钟。
传送门：
题意：n个齿轮，有m(m<n)条边，有两种连接方式： ①2齿轮共轴，这时角速度相等 ②2齿轮共边，这时线速度相等 每对齿轮最多只有一种连接方式 现在给出2种操作： ①修改一个齿轮的半径 ②给予一个齿轮x角速度y，问所有齿轮中角速度最大值(取自然对数ln(ans)) 题解： n个齿轮和m条边可以组成一个森林，对于每个节点只要考虑与它连通的节点即可，因此 这里只考虑一棵树的情况 如果x和y共边，那么能得出log(w[x])=log(w[y])+log(r[y])-log(r[x]) 我们找任意一个节点作为根节点，并且将它作为参照点(就是参考系，速度设为0) 往下更新所有节点的相对速度，然后利用DFS序和线段树维护区间内角速度的最大值 更新一个节点的半径时，分2种情况： ①与父节点共轴，相对于根节点角速度不变，与u共边的节点角速度变小 ②与父节点共边，相对于根节点角速度变小，与u共轴的节点角速度变小 由于log(w[u])=log(w[fa])+log(r[fa])-log(r[u]) log(w[fa])=log(w[gf])+log(r[gf])-log(r[fa]) 与u共边的节点角速度不变 查询时：先找出x所在树中相对角速度的最大值，用最大值减去x的相对角速度，再加上y 注意之前都是取log2，因此输出时要再乘上ln2
#include#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define Log(x) (int)log2(x)using namespace std;typedef long long LL;const int MX = 1e5 + 5;const int INF = 0x3f3f3f3f;struct Edge { int v, w, nxt;} E[MX * 2];int head[MX], rear;int p[MX];int dfn[MX], in[MX], mid[MX], out[MX], tot;int w[MX], r[MX], mark[MX];int Max[MX << 2], add[MX << 2];void init(int n) { for (int i = 1; i <= n; i++) { head[i] = -1; p[i] = i; mark[i] = 0; } rear = tot = 0;}void add_edge(int u, int v, int w) { E[rear].v = v; E[rear].w = w; E[rear].nxt = head[u]; head[u] = rear++;}void dfs(int u, int fa) { dfn[++tot] = u; in[u] = tot; for (int i = head[u]; ~i; i = E[i].nxt) { int v = E[i].v, op = E[i].w; if (v == fa || op == 1) continue; w[v] = w[u]; mark[v] = 1; dfs(v, u); } mid[u] = tot; for (int i = head[u]; ~i; i = E[i].nxt) { int v = E[i].v, op = E[i].w; if (v == fa || op == 2) continue; w[v] = w[u] + r[u] - r[v]; dfs(v, u); } out[u] = tot;}void PushUP(int rt) { Max[rt] = max(Max[rt << 1], Max[rt << 1 | 1]);}void PushDown(int rt) { if (add[rt]) { add[rt << 1] += add[rt]; add[rt << 1 | 1] += add[rt]; Max[rt << 1] += add[rt]; Max[rt << 1 | 1] += add[rt]; add[rt] = 0; }}void build(int l, int r, int rt) { add[rt] = 0; if (l == r) { Max[rt] = w[dfn[l]]; return; } int m = (l + r) >> 1; build(lson); build(rson); PushUP(rt);}int query(int L, int R, int l, int r, int rt) { if (L <= l && R >= r) return Max[rt]; PushDown(rt); int m = (l + r) >> 1; int ret = -INF; if (L <= m) ret = max(ret, query(L, R, lson)); if (R > m) ret = max(ret, query(L, R, rson)); PushUP(rt); return ret;}void update(int L, int R, int val, int l, int r, int rt) { if (L <= l && R >= r) { add[rt] += val; Max[rt] += val; return; } PushDown(rt); int m = (l + r) >> 1; if (L <= m) update(L, R, val, lson); if (R > m) update(L, R, val, rson); PushUP(rt);}int find(int x) { return p[x] == x ? x : (p[x] = find(p[x]));}int main() { //freopen("in.txt","r",stdin); int cas = 0, n, m, q; while (~scanf("%d%d%d", &n, &m, &q)) { printf("Case #%d:\n", ++cas); init(n); for (int i = 1; i <= n; i++) { scanf("%d", &r[i]); r[i] = Log(r[i]); } for (int i = 1, op, u, v; i <= m; i++) { scanf("%d%d%d", &op, &u, &v); add_edge(u, v, op); add_edge(v, u, op); int p1 = find(u), p2 = find(v); if (p1 != p2) p[p2] = p1; } for (int i = 1; i <= n; i++) { if (find(i) == i) { w[i] = 0; mark[i] = 1; dfs(i, -1); } } build(1, n, 1); while (q--) { int op, x, y, t; scanf("%d%d%d", &op, &x, &y); t = Log(y); if (op == 1) { if (mark[x] && mid[x] < out[x]) update(mid[x] + 1, out[x], t - r[x], 1, n, 1); else if (mark[x] == 0) update(in[x], mid[x], r[x] - t, 1, n, 1); r[x] = t; } else { int rt = find(x); int ans = t + query(in[rt], out[rt], 1, n, 1) - query(in[x], in[x], 1, n, 1); printf("%.3f\n", ans * log(2.0)); } } } return 0;}
转载地址：http://gswpn.baihongyu.com/