HDU6039 Gear Up

发表于 | 阅读数

题意

给$n$个齿轮，每个齿轮之间有两种连接方式，角速度相同，或线速度相同。构成森林（多个树）
有$q$个询问，一个修改半径，一个给定一个齿轮角速度求所连齿轮中最大角速度。

首先我们可以求出所有齿轮对于他的根的相对角速度，由于是乘法并且最后输出对数。我们可以对所以取$log2$，然后相对角速度的计算就成乘法变成除法。
然后看第一个角速度连接方式。一条角边链上的齿轮，修改半径对其链无法造成影响。
再看看第二个线速度连接方式。一条线边链上的齿轮，因为$w=\frac{w_{根}*r_{根}}{r_{自己}}$ 会对自己的角速度产生影响。

  • 对在角边链上的点（父亲是角边的点），自己的角速度不变，线速度发生改变，影响了他的线边。
  • 对在线边链上的点（父亲是线边的点），自己的角速度发生，线速度不变，影响了自己和他的角边。

此时用$dfs$序记录下他的儿子角边，儿子线边就好了，用线段树修改。

注意点：

  • 他是一个森林（不是一棵树，而是多棵树，查询需要并查集判断在那棵树）
  • 根结点因为角速度是定的，就相当于连上一个角边
  • 线段树查询是记住判断$(l<=r)!!!!!!!!$
    代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int c[N];
struct tr
{
    int l, r, lazy, maxx;
} tree[N << 2];
void pushdown(int pos)
{
    if (tree[pos].lazy)
    {
        int w = tree[pos].lazy;
        tree[pos * 2].maxx += w;
        tree[pos * 2 + 1].maxx += w;
        tree[pos * 2].lazy += w;
        tree[pos * 2 + 1].lazy += w;
        tree[pos].lazy = 0;
    }
}
void pushup(int pos)
{
    tree[pos].maxx = max(tree[pos * 2].maxx, tree[pos * 2 + 1].maxx);
}
void build(int l, int r, int pos)
{
    tree[pos].l = l;
    tree[pos].r = r;
    tree[pos].maxx = -1e9;
    if (l == r)
    {
        tree[pos].maxx = c[l];
        return;
    }
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    build(l, mid, pos * 2);
    build(mid + 1, r, pos * 2 + 1);
    pushup(pos);
}
void add(int l, int r, int w, int pos)
{
    if (l <= tree[pos].l && tree[pos].r <= r)
    {
        tree[pos].maxx += w;
        tree[pos].lazy += w;
        return;
    }
    pushdown(pos);
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if (l <= mid)
        add(l, r, w, pos * 2);
    if (r > mid)
        add(l, r, w, pos * 2 + 1);
    pushup(pos);
}
int quary(int l, int r, int pos)
{
    if (l <= tree[pos].l && tree[pos].r <= r)
    {
        return tree[pos].maxx;
    }
    pushdown(pos);
    int maxx = -1e9;
    int mid = (tree[pos].l + tree[pos].r) >> 1;
    if (l <= mid)
        maxx = max(maxx, quary(l, r, pos * 2));
    if (r > mid)
        maxx = max(maxx, quary(l, r, pos * 2 + 1));
    return maxx;
}
struct node
{
    int to, flag;
} e;
vector<node> g[N];
int cnt, l[N], r[N], mid[N], f[N], b[N], mark[N];
void addedge(int x, int to, int w)
{
    e.to = to;
    e.flag = w;
    g[x].push_back(e);
}
void dfs(int x, int f, int dis)
{
    //cout <<x<<" "<<dis<<endl;
    l[x] = ++cnt;
    c[cnt] = dis;
    for (int i = 0; i < g[x].size(); i++)
    {
        int to = g[x][i].to;
        int flag = g[x][i].flag;
        if (to == f)
            continue;
        if (flag == 2)
            dfs(to, x, dis), mark[to] = flag;
    }
    mid[x] = cnt;
    for (int i = 0; i < g[x].size(); i++)
    {
        int to = g[x][i].to;
        int flag = g[x][i].flag;
        if (to == f)
            continue;
        if (flag == 1)
            dfs(to, x, dis + (b[x] - b[to])), mark[to] = flag;
    }
    r[x] = cnt;
}
int find(int x)
{
    if (f[x] != x)
        return f[x] = find(f[x]);
    return x;
}
void unon(int x, int y)
{
    int xx = find(x);
    int yy = find(y);
    if (xx != yy)
    {
        f[xx] = yy;
    }
}
int n, m, q;
int main()
{
    int t = 0;
    while (~scanf("%d%d%d", &n, &m, &q))
    {
        cnt = 0;
        t++;
        for (int i = 1; i <= n; i++)
            g[i].clear(), f[i] = i, mark[i] = 0;
        memset(tree, 0, sizeof(tree));
        for (int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &x);
            b[i] = int(log(x) / (log(2) * 1.0));
            //cout<<b[i]<<endl;
        }
        for (int i = 1; i <= m; i++)
        {
            int a, x, y;
            scanf("%d%d%d", &a, &x, &y);
            addedge(x, y, a);
            addedge(y, x, a);
            unon(x, y);
        }
        for (int i = 1; i <= n; i++)
            if (find(i) == i)
            {
                dfs(i, 0, 0);
            }
        build(1, cnt, 1);
        printf("Case #%d:\n", t);
        for (int i = 1; i <= q; i++)
        {
            int a, x, y;
            scanf("%d%d%d", &a, &x, &y);

            if (a == 1)
            {
                y = int(log(y) / (log(2) * 1.0));
                //cout<<b[x]<<endl;
                if (mark[x] == 1)
                    add(l[x], mid[x], b[x] - y, 1);
                else
                    add(mid[x] + 1, r[x], y - b[x], 1); //¸üÐÂÏß±ß
                b[x] = y;
            }
            else
            {
                int k = find(x);
                y = int(log(y) / (log(2) * 1.0));
                int ans = y - quary(l[x], l[x], 1) + quary(l[k], r[k], 1);
                printf("%.3f\n", ans * log(2.0));
            }
           
        }
    }
}

</details>