G

题目要求从任意点出发能走的最远距离，观察到一段路程内所有点一定都以唯一一点为终点

如:

障碍数组n1 n2 n3 n4 n5为5 0 0 2 0

则n2,n3,n4都会以n4为终点

因此参考并查集递归实现路径压缩编写代码

对于本题来说，相较于用map/set实现的代码，本方法在内存占用上有显著优势，但运行时间基本无差异

附上代码:

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int b[1000005];//去往的最远距离
int n,m;
inline int read(void)
{
    int ans=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return f?-ans:ans;
}
int further(int pos){
    int to=b[pos];
    if(a[to]<=0&&pos<n){
        b[pos]=further(to+1);
    }
    return b[pos];
}
int main(){
    int index,i,p,x;
    n=read();
    m=read();
    for(i=1;i<=n;i++){
        a[i]=read();
        b[i]=i;
    }
    for(i=0;i<m;i++){
        index=read();
        if(index==1){
            p=read();
            x=read();
            if(a[p]<=0)    continue;
            a[p]-=x;
        }
        else{
            p=read();
            b[p]=further(b[p]);
            cout<<b[p]<<endl;
        }
    }
}