loj6435. "PKUSC 2018"스타크래프트

제목의 뜻

생략

문제풀이

이 문제를 푸는 느낌: 어려워, 묘해, 난 못해.우선, 한 점\(x\) 에서 다른\(y\) (\(x > y\) 까지 가장 좋은 방법이 두 가지밖에 없다는 결론을 명확히 해야 한다. 왼쪽으로 가든지, 오른쪽으로 가든지, 한 걸음 오른쪽으로 가든지, 왼쪽으로 가든지.폭력적이면\(\mathcal O(n ^ 2)\)의 dp를 통해 예처리와\(\mathcal O(n)\)를 한 번에 물어볼 수 있습니다.여기서 dp 배열은\(f {i, j}\) 대표 점\(i\) 걸음\(j\) 걸음을 처리하고\(i\) 왼쪽의 가장 왼쪽 점(\([f {i, j}, i]\) 이 포함된 구간의 점은\(i\) 걸음부터\(j\) 걸음을 초과하지 않아도 다 갈 수 있습니다.어떻게 최적화합니까?배증으로 완성할 수 있을까?좀 어려울 것 같습니다.그러나 상태를 설정할 수 있습니다. 명령\(f {i, j}\) 는 구간\([i, n]\) 의 점을\(2 ^ j\) 보로 표시하고\(i\) 왼쪽의 가장 왼쪽 점까지 갈 수 있습니다.이렇게 하면\[f {i, 0} =\max(f {i + 1, 0}, l i)\f {i, j} = f {f {i, j - 1}\\\, j - 1}\\\\\] 로 전환됩니다. 그러나 이렇게 하면 문의의 복잡도를 최적화할 수 없습니다.함수\(C (l, x)\) 를\(x\) 에서\([l, x)\) 까지의 모든 점의 총 걸음수를 고려하면, 한 번에 물어보는 것은\(C (l, x) - C (r + 1, x)\) 입니다.\(C (l, x)\) 를 어떻게 계산합니까?\(x\) 에서 한 걸음 먼저 걷고, 비용이 1이 들면\([l x, n]\) 의 모든 점까지 갈 수 있습니다.이때\(2 ^ i\) 단계를 더 가면 구간\([f {l x, 2 ^ i}, n]\) 의 임의의 지점에 도달할 수 있습니다.우리는\(x\)에서 멀어질수록 더 많은 걸음걸이가 필요하다는 결론을 발견할 수 있다. 따라서 우리는 2분을 통해 분단점을 찾을 수 있다.이를 위해 우리는\(s {x, i}\) (x\)가\([f {x, i}, x]\([f {x, i}, i}, x]\)([s {i, 0} = i - f {i, 0}\s {i, j} =s {i, j- -1} + s {i, j- 1} + s {f {f {f {x x]) 이 필요한 왼쪽으로 가는 총 보수를 미리 처리해야 하며,\[s (s {x {x i} i} {i} {{{i} {{i, i} {{} {{{{{{{} {{각 점에 대해 2진법으로 나누어 모든 공헌을 더해라.그러나 전체 구간\([l, x-1]\)의 점에 대해 이진 분할을 동시에 할 수 있음을 발견했습니다. 이것은 단조로우므로 미리 처리된\(s\) 그룹을 사용해야 합니다.복잡성\(\mathcal O (n + q)\log2 n)\).

#include 
#define fi first
#define se second
using namespace std;
typedef long long ll;

const int N = 3e5 + 5, M = 19;
int n, q, arr[N];
int f[M][N]; ll s[M][N];
int lg2 (int x) {
    return 32 - __builtin_clz(x);
}
ll solve (int o, int x) {
    if (arr[x] <= o) {
        return x - o;
    }
    int co = 1; ll ret = x - arr[x]; x = arr[x];
    for (int i = M - 1; ~i; --i) {
        if (f[i][x] > o) {
            ret += s[i][x] + 1ll * co * (x - f[i][x]);
            x = f[i][x], co += 1 << i;
        }
    }
    return ret + 1ll * (co + 1) * (x - o);
}
int main () {
    scanf("%d", &n), arr[1] = 1;
    for (int i = 2; i <= n; ++i) {
        scanf("%d", &arr[i]);
    }
    f[0][n] = arr[n], s[0][n] = n - f[0][n];
    for (int i = n - 1; i; --i) {
        f[0][i] = min(f[0][i + 1], arr[i]), s[0][i] = i - f[0][i];
    }
    for (int j = 1; j < lg2(n); ++j) {
        for (int i = n; i; --i) {
            if (f[j - 1][i]) {
                f[j][i] = f[j - 1][f[j - 1][i]];
                s[j][i] = s[j - 1][i] + s[j - 1][f[j - 1][i]] + (1ll << (j - 1)) * (f[j - 1][i] - f[j - 1][f[j - 1][i]]);
            }
        }
    }
    scanf("%d", &q);
    for (int i = 1, l, r, x; i <= q; ++i) {
        scanf("%d%d%d", &l, &r, &x);
        ll ouo = solve(l, x) - solve(r + 1, x), ovo = r - l + 1, g = __gcd(ouo, ovo);
        printf("%lld/%lld
", ouo / g, ovo / g);
    }
    return 0;
}