「PKUSC2018」星际穿越

时间:2024-11-02 18:04:19

传送门

Solution 

倍增

Code 

#include <bits/stdc++.h>
#define reg register
#define ll long long using namespace std; int read() {
int x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch <= '9' && ch >= '0') {
x = (x << 1) + (x << 3) + ch - '0';
ch = getchar();
}
return x * f;
} const int MN = 3e5 + 5; int gcd(int x, int y) { return !y ? x : gcd(y, x % y); } int N, l[MN];
int p[MN][20], v[MN][20]; int cal(int L, int x) {
if (L == x)
return 0;
if (L >= l[x])
return x - L;
int r = x - L, step = 0, i;
for (x = l[x], i = 18; ~i; --i)
if (p[x][i] >= L) {
r += v[x][i] + (x - p[x][i]) * step;
step += 1 << i;
x = p[x][i];
}
r += (x - L) * (step + 1);
return r;
} int main() {
N = read();
reg int i, j;
for (l[1] = 0, i = 2; i <= N; ++i) l[i] = read();
for (p[N][0] = l[N], i = N - 1; i; --i) p[i][0] = min(l[i], p[i + 1][0]);
for (j = 1; j <= 18; ++j)
for (i = 1; i <= N; ++i)
if (p[i][j - 1])
p[i][j] = p[p[i][j - 1]][j - 1]; for (i = 1; i <= N; ++i) v[i][0] = i - p[i][0];
for (j = 1; j <= 18; ++j)
for (i = 1; i <= N; ++i)
if (p[i][j])
v[i][j] = v[i][j - 1] + v[p[i][j - 1]][j - 1] + (p[i][j - 1] - p[i][j]) * (1 << (j - 1)); int Q = read(), L, R, x;
while (Q--) {
L = read(), R = read(), x = read();
int P = cal(L, x) - cal(R + 1, x), q = R - L + 1;
int g = gcd(P, q);
printf("%d/%d\n", P / g, q / g);
}
return 0;
}

Blog来自PaperCloud,未经允许,请勿转载,TKS!