企业官网建设流程全解析

题目描述

小 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是否有引用，以及所引用的消息编号。如果ri>0r_i > 0ri​>0，则消息iii为引用了消息rir_iri​；如果ri=0r_i = 0ri​=0，则消息iii没有引用消息。

消息记录里有非常多条消息。为了快速查找所需要的消息，小 A 准备实现一个简单的消息查找工具。消息查找工具任意时刻只能定位恰好一条消息，如果当前位于消息iii(1<i≤n1 < i \le n1<i≤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​(yk<xky_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

输入 #1

6 3 0 0 1 2 2 5 4 1 6 2 6 3

输出 #1

2 2 3

输入输出样例 #2

输入 #2

5 5 0 0 0 1 3 4 1 4 2 5 1 5 2 5 3

输出 #2

1 2 2 2 1

说明/提示

数据范围

对于40%40\%40%的测试点，保证1≤n≤20001 \le n \le 20001≤n≤2000，1≤q≤20001 \le q \le 20001≤q≤2000。

对于所有测试点，保证1≤n≤1051 \le n \le 10^51≤n≤105，1≤q≤1051 \le q \le 10^51≤q≤105，0≤ri<i0 \le r_i < i0≤ri​<i，1≤yk<xk≤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​的引用时，分两种情况：

1. 区间[i,ri][i,r_i][i,ri​]与区间[j,rj][j,r_j][j,rj​]互不相交或首尾相接，此时的节省的步数就要再加上一个j−rj−1j-r_j-1j−rj​−1
2. 区间[i,ri][i,r_i][i,ri​]与区间[j,rj][j,r_j][j,rj​]相交，此时只能选取一个区间，节省的步数为两者之一

此时定义ggg数组，gig_igi​为从iii到yyy能节省的最大步数，gy=0g_y=0gy​=0

这里当i点没有引用消息时，gi=gi−1g_i=g_{i-1}gi​=gi−1​

而当i点有引用消息时，gi=max(gi−1,gri+(i−ri−1))g_i=max(g_{i-1},g_{r_i}+(i-r_i-1))gi​=max(gi−1​,gri​​+(i−ri​−1))，不过要注意，这里引用消息必须要大于等于yyy，所以还要加一个判断，此时的代码为：

g[y]=0;for(inti=y+1;i<=n;i++){if(r[i]!=0&&r[i]>=y){g[i]=max(g[i-1],g[r[i]]+(i-r[i]-1));}else{g[i]=g[i-1];}}

但由于n，qn，qn，q都为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)

具体代码如下：

#include<bits/stdc++.h>usingnamespacestd;intn,q;intr[100005],f[100005],g[100005];vector<pair<int,int>>a;intmain(){cin>>n>>q;for(inti=1;i<=n;i++){cin>>r[i];if(r[i]!=0){f[i]=i;a.push_back({i,r[i]});}else{f[i]=f[i-1];}}while(q--){intx,y;cin>>x>>y;g[y]=0;for(inti=0;i<a.size();i++){intst=a[i].first,ed=a[i].second;if(ed>=y){g[st]=max(g[f[st-1]],g[f[ed]]+(st-ed-1));//这里由于st已经是引用消息了，就不需要用f数组了}else{g[st]=g[f[st-1]];}}cout<<x-y-(g[f[x]])<<'\n';//最终步数为基本步数减去节省步数}return0;}