题目描述小 A 的消息记录中有nnn条消息依次以1,2,…,n1, 2, \dots, n1,2,…,n编号。编号小的消息发送时间早于编号大的消息。一条消息可以引用一条编号小于它的消息也可以不引用消息。小 A 注意到消息记录里有引用的消息数量不会非常多。消息记录的一个例子是【消息 1】小 A有人做了今天的第一题吗【消息 2】小 A我第一题 WA 了可能是什么原因【消息 3引用消息 1】小 B我我我【消息 4引用消息 2】小 C我也 WA 了【消息 5引用消息 2】小 B是不是没开 long long【消息 6引用消息 5】小 A改了就 AC 了太厉害了对于消息iii(1≤i≤n1 \le i \le n1≤i≤n)小 A 以rir_iri​标记消息iii是否有引用以及所引用的消息编号。如果ri0r_i 0ri​0则消息iii为引用了消息rir_iri​如果ri0r_i 0ri​0则消息iii没有引用消息。消息记录里有非常多条消息。为了快速查找所需要的消息小 A 准备实现一个简单的消息查找工具。消息查找工具任意时刻只能定位恰好一条消息如果当前位于消息iii(1i≤n1 i \le n1i≤n)那么接下来可以选择以下两种操作之一定位到消息i−1i - 1i−1如果消息iii引用了消息rir_iri​定位到消息rir_iri​。以上操作可以执行任意次包括零次。小 A 有qqq次询问。在第kkk(1≤k≤q1 \le k \le q1≤k≤q) 次询问中小 A 给出消息编号xk,ykx_k, y_kxk​,yk​(ykxky_k x_kyk​xk​)。小 A 想知道如果当前消息查找工具位于xkx_kxk​至少需要多少次操作才能定位到消息yky_kyk​。输入格式第一行两个正整数n,qn, qn,q分别表示消息条数与询问次数。第二行nnn个非负整数r1,r2,…,rnr_1, r_2, \dots, r_nr1​,r2​,…,rn​表示消息的引用关系具体含义见题目描述。接下来qqq行中的第kkk行 (1≤k≤q1 \le k \le q1≤k≤q) 包含两个正整数xk,ykx_k, y_kxk​,yk​表示一次询问。保证至多只有 1000 条引用消息。输出格式输出qqq行每行一个整数表示将界面从消息xkx_kxk​切换到消息yky_kyk​所需的最少操作次数。输入输出样例 #1输入 #16 3 0 0 1 2 2 5 4 1 6 2 6 3输出 #12 2 3输入输出样例 #2输入 #25 5 0 0 0 1 3 4 1 4 2 5 1 5 2 5 3输出 #21 2 2 2 1说明/提示数据范围对于40%40\%40%的测试点保证1≤n≤20001 \le n \le 20001≤n≤20001≤q≤20001 \le q \le 20001≤q≤2000。对于所有测试点保证1≤n≤1051 \le n \le 10^51≤n≤1051≤q≤1051 \le q \le 10^51≤q≤1050≤rii0 \le r_i i0≤ri​i1≤ykxk≤n1 \le y_k x_k \le n1≤yk​xk​≤n保证至多有 1000 条引用消息。思路在没有任何引用的情况下要从xxx到yyy的步数为x−yx-yx−y而在有一个从iii到rir_iri​的引用时步数减少了i−ri−1i-r_i-1i−ri​−1的步数也就是节省了i−ri−1i-r_i-1i−ri​−1的步数而如果又有一个从jjj到rjr_jrj​的引用时分两种情况区间[i,ri][i,r_i][i,ri​]与区间[j,rj][j,r_j][j,rj​]互不相交或首尾相接此时的节省的步数就要再加上一个j−rj−1j-r_j-1j−rj​−1区间[i,ri][i,r_i][i,ri​]与区间[j,rj][j,r_j][j,rj​]相交此时只能选取一个区间节省的步数为两者之一此时定义ggg数组gig_igi​为从iii到yyy能节省的最大步数gy0g_y0gy​0这里当i点没有引用消息时gigi−1g_ig_{i-1}gi​gi−1​而当i点有引用消息时gimax(gi−1,gri(i−ri−1))g_imax(g_{i-1},g_{r_i}(i-r_i-1))gi​max(gi−1​,gri​​(i−ri​−1))不过要注意这里引用消息必须要大于等于yyy所以还要加一个判断此时的代码为g[y]0;for(intiy1;in;i){if(r[i]!0r[i]y){g[i]max(g[i-1],g[r[i]](i-r[i]-1));}else{g[i]g[i-1];}}但由于nqnqnq都为10510^5105此时的时间复杂度为O(nq)O(nq)O(nq)会TLETLETLE所以需要优化优化我们注意到题目中有这么一句话保证至多有 1000 条引用消息。而我们的代码中实际需要计算的ggg只有引用消息的消息所以我们更改ggg的含义gig_igi​表示上一个引用消息为iii的消息的节省步数同时需要再开一个f数组来维护每个消息上一个引用消息的位置也就是fif_ifi​为消息iii之前的第一个引用消息这个fff数组的维护是可以在输入rrr数组就提前预处理好的此时我们只需记录下每个引用消息的位置和引用完的位置在转移ggg时只需遍历这个记录下的数组即可时间复杂度为O(1000q)O(1000q)O(1000q)具体代码如下#includebits/stdc.husingnamespacestd;intn,q;intr[100005],f[100005],g[100005];vectorpairint,inta;intmain(){cinnq;for(inti1;in;i){cinr[i];if(r[i]!0){f[i]i;a.push_back({i,r[i]});}else{f[i]f[i-1];}}while(q--){intx,y;cinxy;g[y]0;for(inti0;ia.size();i){intsta[i].first,eda[i].second;if(edy){g[st]max(g[f[st-1]],g[f[ed]](st-ed-1));//这里由于st已经是引用消息了就不需要用f数组了}else{g[st]g[f[st-1]];}}coutx-y-(g[f[x]])\n;//最终步数为基本步数减去节省步数}return0;}