#include bits/stdc .h const int T 8e6 10, N 3e5 10;int ri() { char c getchar(); int x 0, f 1; for(;c 0 || c 9 ; c getchar()) if(c - ) f -1; for(;c 0 c 9 ; c getchar()) x (x 1) (x 3) - 0 c; return x * f;int s[T], tg[T], ls[T], rs[T], l[N], mn[N], rt[N], sz, n;void Ins(int np, int lp, int L, int R, int st, int ed) { s[np sz] s[lp] ed - st 1; tg[np] tg[lp]; ls[np] ls[lp]; rs[np] rs[lp]; if(L st ed R) return void( tg[np]); int m L R 1;  if(st m) Ins(ls[np], ls[lp], L, m, st, std::min(ed, m)); if(ed m) Ins(rs[np], rs[lp], m 1, R, std::max(m 1, st), ed);int Que(int p, int L, int R, int st, int ed) { if(L st ed R || !p) return s[p]; int m L R 1, r tg[p] * (ed - st 1); if(st m) r Que(ls[p], L, m, st, std::min(ed, m)); if(ed m) r Que(rs[p], m 1, R, std::max(m 1, st), ed); return r;int main() { n ri();  for(int i 2;i n; i) l[i] ri(); mn[n] l[n]; for(int i n - 1; i; --i) mn[i] std::min(mn[i 1], l[i]); for(int i 2;i n; i)  Ins(rt[i], rt[mn[i]], 1, n, 1, i - 1); for(int m ri();m--;) { int L ri(), R ri(), x ri(), p R - L 1, q p; if(L l[x]) p Que(rt[l[x]], 1, n, L, std::min(R, l[x] - 1)); int d std::__gcd(p, q); printf( %d/%d\\n , p / d, q / d); return 0;

然而这个方法bzoj上T了。
考虑优化之 可以采用离线 树状数组的方法。

#include bits/stdc .h const int N 3e5 10;int ri() { char c getchar(); int x 0, f 1; for(;c 0 || c 9 ; c getchar()) if(c - ) f -1; for(;c 0 c 9 ; c getchar()) x (x 1) (x 3) - 0 c; return x * f;int pr[N], nx[N], Pr[N], Nx[N], l[N], p[N], q[N], tp, mn[N], rt[N], sz, n;void add(int u, int i) {nx[i] pr[u]; pr[u] i;}struct Q {int l, r, id;}To[N];void AQ(int u, int l, int r, int id) { To[ tp].l l; To[tp].r r; To[tp].id id; Nx[tp] Pr[u]; Pr[u] tp; struct B { int t1[N], t2[N]; void A(int i, int v) {for(int x i;x n;x x -x) t1[x] v, t2[x] 1LL * v * i;} int Q(int i) { int r1 0, r2 0; for(int x i;x; x - x -x) r1 t1[x], r2 t2[x]; return r1 * (i 1) - r2; void A(int l, int r, int v) {A(l, v); A(r 1, -v);} int Q(int l, int r) {return Q(r) - Q(l - 1);}void Dfs(int u) { if(u ! 1) T.A(1, u - 1, 1);  for(int i Pr[u]; i; i Nx[i]) p[To[i].id] T.Q(To[i].l, To[i].r); for(int i pr[u]; i; i nx[i]) Dfs(i);  if(u ! 1) T.A(1, u - 1, -1);int main() { n ri();  for(int i 2;i n; i) l[i] ri(); mn[n] l[n]; add(mn[n], n); for(int i n - 1; i 1; --i) mn[i] std::min(mn[i 1], l[i]), add(mn[i], i); int m ri(); for(int i 1;i m; i) { int L ri(), R ri(), x ri(); p[i] q[i] R - L 1; if(L l[x]) AQ(l[x], L, std::min(R, l[x] - 1), i); Dfs(1); for(int i 1;i m; i) { int d std::__gcd(p[i], q[i]); printf( %d/%d\\n , p[i] / d, q[i] / d); return 0;

愉快地卡了过去

记录