Description
详见OJ
Solution
看了\(0.5h\)的题目,最后才大概明白了题目内容。
大概是求一条链的最小值,但不知道有没有还钱以后边是否还存在。
然后就没打了。
正解是倍增+并查集。
并查集得出\(x\)的祖宗以及深度,便于判断两个点是否在同一棵树以及深度。
由于强制在线,我们更新的时候可以直接更新,但不用更新完。
在查询的时候我们再对需要的更新(用递归更新)即可。(真的不想说什么,感觉这题在这套题里是最水的,可惜考场没看懂题意)
Code
#include <cstdio>
#include <cstring>
#define N 100010
#define mem(x, a) memset(x, a, sizeof x)
#define fo(x, a, b) for (int x = a; x <= b; x++)
#define fd(x, a, b) for (int x = a; x >= b; x--)
#define min(x, y) (x < y ? x : y)
#define max(x, y) (x > y ? x : y)
using namespace std;
int n, m, opt, a, b, c, ans = 0;
int fa[N][18], mi[N][18], mx[N], fat[N][2];
inline int read()
{
int x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return x;
}
int gf(int x)
{
int getfa = 0;
if (fat[x][0] == x) return x;
getfa = gf(fat[x][0]);
fat[x][1] += fat[fat[x][0]][1];
return fat[x][0] = getfa;
}
void dfs(int x, int y)
{
if (mx[x] >= y) return;
fo(i, mx[x] + 1, y)
{
dfs(fa[x][i - 1], i - 1);
fa[x][i] = fa[fa[x][i - 1]][i - 1];
mi[x][i] = min(mi[x][i - 1], mi[fa[x][i - 1]][i - 1]);
}
mx[x] = y;
}
void LCA(int x, int y)
{
ans = 1e6;
for (int i = 0, cha = fat[x][1] - fat[y][1]; cha; cha >>= 1, i++)
if (cha & 1) dfs(x, i), ans = min(ans, mi[x][i]), x = fa[x][i];
if (x != y) ans = 0;
}
int main()
{
freopen("money.in", "r", stdin);
freopen("money.out", "w", stdout);
n = read(), m = read();
fo(i, 1, n) fat[i][0] = i;
while (m--)
{
opt = read(), a = read(), b = read();
a = (a + ans) % n + 1; b = (b + ans) % n + 1;
if (opt == 0)
{
c = read();
c = (c + ans) % n + 1;
fa[a][0] = b, mi[a][0] = c;
fat[a][0] = b, fat[a][1] = 1;
}
else
{
if (gf(a) != gf(b) || fat[a][1] <= fat[b][1]) ans = 0;
else LCA(a, b);
printf("%d\n", ans);
}
}
return 0;
}