坐标轴上有 nn 个星球,第 ii 个星球坐标为 ii ,与星球 [li,i−1][l_i , i - 1] 之间都有双向通道。其中,经过每个通道都需要 1 的单位时间。

定义dist(x,y)dist(x, y)为从星球xx出发到达星球yy的最短时间，求∑i=lrdist(x,i)\displaystyle \sum_{i=l}^{r}dist(x, i)

多组询问，保证l<r<xl < r < x

n,q≤3×105n, q\le 3\times 10^5

LOJ6435

Solution

设L[i]=minj=inlj\displaystyle L[i] = \min_{j=i}^{n}l_j，考虑从xx走到yy（x>yx > y）的最短路，除了第一步外，后面的每一步都是沿着L[i]L[i]走

若某一步不走L[i]L[i]更优，那么就说明[i+1,n][i + 1, n]内存在一个更小的ljl_j，矛盾

先不管第一步，因为(L[i],i)(L[i], i)形成了一个树型结构，显然可以用主席树维护答案

每个点存它的最短路，再求和，因为要区间求和，所以要标记永久化

也可以离线，直接线段树维护

再考虑第一步：

  • 若y∈[lx,x−1]y\in[l_x, x - 1]，则一步就能到
  • 否则，第一步肯定往[lx,n][l_x, n]中ljl_j最小的jj去跳，然后第二步就能跳到L[lx]L[l_x]

随便处理下就可以了

Code

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
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 3e5 + 100;

int N, Q;
int l[Maxn], L[Maxn];

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls node[o].ch[0]
#define rs node[o].ch[1] 
#define lson ls, l, mid
#define rson rs, mid + 1, r
	struct info
	{
		int ch[2], tag;
		LL sum;
	} node[Maxn * 80];
	int node_cnt;

	inline void push_up (int o) { node[o].sum = node[ls].sum + node[rs].sum; }

	inline void update (int pre, int &o, int l, int r, int x, int y)
	{
		o = ++node_cnt; node[o] = node[pre];
		if (x <= l && r <= y) { node[o].sum += r - l + 1; ++node[o].tag; return ; }
		if (x <= mid) update (node[pre].ch[0], lson, x, y);
		if (y > mid) update (node[pre].ch[1], rson, x, y);
		push_up (o);
	}

	inline LL query (int o, int l, int r, int x, int y)
	{
		if (x > y) return 0;
		if (x <= l && r <= y) return node[o].sum;
/**/	LL ans = (LL) node[o].tag * (min (y, r) - max (x, l) + 1);
		if (x <= mid) ans += query (lson, x, y);
		if (y > mid) ans += query (rson, x, y);
		return ans;
	}

#undef mid
}

int O[Maxn];

inline void Init ()
{
	L[N + 1] = 0x3f3f3f3f;
	for (int i = N; i >= 2; --i) L[i] = min (L[i + 1], l[i]);
	for (int i = 2; i <= N; ++i) SEG :: update (O[L[i]], O[i], 1, N, 1, i - 1);
}

inline void Solve ()
{
	Init ();
	Q = read<int>();
	while (Q--)
	{
		int nl = read<int>(), nr = read<int>(), x = read<int>();
		LL down = nr - nl + 1, up = nr - nl + 1;
		up += SEG :: query (O[l[x]], 1, N, nl, min (nr, l[x] - 1));
		LL g = __gcd (up, down);
		printf("%lld/%lld\n", up / g, down / g);
	}
}

inline void Input ()
{
	N = read<int>();
	for (int i = 2; i <= N; ++i) l[i] = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("A.in", "r", stdin);
	freopen("A.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}