loj6435

题意

log

做法一

结论1：((jin[1,i))dis(i,j))是单调不升的

显然

考虑(i)向左那些点走的方法，(dis(i,j)=1)的这些点显然是直接与(i)相连的
然后发现距离为(2)的那些点方法有点奇怪，既可以(i)向左走两步，也可以(i)向右走一步再向左走一步
对走的方法找一找结论

显然的，向右走只有可能是一开始，一旦向左走就不会回头了
结论2：不会存在向右超过一步的情况

证明：
考虑向右走的最后一步，然后向左走，若不走到(i)左边显然没有意义
若走到(i)左边了，显然其也是与(i)直接相连的，故可以一开始直接走到那个点，再向左走

结论3：(dis(i,j)le 2(jin[1,i)))的充要条件为距离([l_i,n])某一点距离不超过(1)
推论：(dis(i,j)le k(jin[1,i)))的充要条件为距离([l_i,n])某一点距离不超过(k-1)

然后自然的倍增来做

做法二

这个就比较简单了，没那么多细节
直接维护对于每个(i)，([1,i))走进([i,n])的最短路径
那怎么维护这个东西呢。令(mn_i=min{l_j|jin[i,n]})
假设已经得到了([1,mn_i))走进([mn_i,n])的最短路径，则([1,i))走到([i,n])的最短路径只要在其基础上([1,i))加(1)即可

正确性：
一开始([1,mn_i))只能走进([mn_i,i))，因为如果能走进([i,n])，则(mn_i)会左移

然后这个主席树维护即可

那么查询(l,r,x)时，就查询([l_x,n])维护的东西

code（做法一）

这题实现来讲有些细节，拉一份这里的代码，这篇题解也写的挺好的

#include <bits/stdc++.h>
#define N 300005
#define LN 20
#define ID isdigit(c = *next++)

struct Istream {
	char *next, buf[20030731];
	void init(FILE *f = stdin) {fread(buf, 1, sizeof buf, f); next = buf;}
	Istream & operator >> (int &x) {
		int c; x = 0;
		for (; !ID; ) if (!~c) return *this;
		for (x = c & 15; ID; x = x * 10 + (c & 15)) if (!~c) break;
		return *this;
	}
} cin;

struct Ostream {
	char *next, buf[20030731], _buf[34];
	Ostream () {next = buf;}
	void flush(FILE *f = stdout) {fwrite(buf, 1, next - buf, f); next = buf;}
	Ostream & operator << (long long x) {
		if (!x) return put(48), *this;
		int i;
		for (i = 0; x; x /= 10) _buf[++i] = x % 10 | 48;
		for (; i; --i) put(_buf[i]);
		return *this;
	}
	Ostream & operator << (char c) {return put(c), *this;}
	void put(char c) {*next++ = c;}
} cout;

typedef long long ll;

int n, q;
int l[N];
int P[LN][N], *p = *P;
ll s[LN][N];

inline void down(int &x, const int y) {x > y ? x = y : 0;}

ll solve(int u, int v) {
	if (u >= l[v]) return std::max(v - u, 0);
	int i, cur = 1; ll res = v - l[v]; v = l[v];
	for (i = LN - 1; i >= 0; --i)
		if (P[i][v] > u) {
			res += s[i][v] + (ll)(v - P[i][v]) * cur;
			cur += 1 << i; v = P[i][v];
		}
	return res + (v - u) * (cur + 1);
}

int main() {
	int i, u, v; ll num, den, d;
	cin.init();
	cin >> n;
	for (i = 2; i <= n; ++i) cin >> l[i]; p[n + 1] = INT_MAX;
	for (i = n; i > 1; --i) {
		p[i] = std::min(l[i], p[i + 1]);
		s[0][i] = i - p[i];
	}
	for (v = 2; v <= n; ++v)
		for (i = 0; i < LN - 1; ++i) {
			P[i + 1][v] = P[i][P[i][v]];
			s[i + 1][v] = s[i][v] + s[i][P[i][v]] + ((ll)(P[i][v] - P[i + 1][v]) << i);
		}
	for (cin >> q; q; --q) {
		cin >> u >> v >> i;
		num = solve(u, i) - solve(v + 1, i);
		d = std::__gcd(num, den = v - u + 1);
		cout << num / d << '/' << den / d << '
';
	}
	cout.flush();
	return 0;
}