题解

#include<bits/stdc++.h>
using namespace std;
const int N=200001;
int n,c,m,a[N],bl[N],st[N],ed[N],pla[N],num[N],siz[N],ans1,ans2;
inline int get(){//快读
    char ch=getchar();
	int sum=0,fl=1;
    while(ch<'0'||ch>'9'){
        ch=getchar();
        if(ch=='-') 
			fl=-1;
	}
    while(ch>='0'&&ch<='9')
        sum*=10,sum+=ch-'0',ch=getchar();
    return sum*fl;
}
inline void build(){//分块
    int sum=sqrt(n);
    for(register int i=1;i<=sum;++i)
        st[i]=(n/sum)*(i-1)+1,ed[i]=(n/sum)*i;
    ed[sum]=n;
    for(register int i=1;i<=sum;++i){
        for(register int j=st[i];j<=ed[i];++j)
            bl[j]=i;	 
    }
    for(register int i=1;i<=sum;++i)
		for(register int j=ed[i];j>=st[i];--j){
			if(a[j]+j>ed[i])
				num[j]=1,pla[j]=a[j]+j;
			else	
				num[j]=num[j+a[j]]+1,pla[j]=pla[j+a[j]];//预处理
		}
    return;   
}
inline void ask(int x){//查询
	int tim=0;
   	for(register int i=x;i<=n;i=pla[i])
   		tim+=num[i],ans1=i;
   	for(register int i=ans1;i<=n;i+=a[i]){
   		if(i+a[i]>n)
   			ans1=i;
	   }	
   	ans2=tim;
}
inline void modify(int x,int y){ //修改
	a[x]=y;
	int blx=bl[x];
	for(register int i=x;i>=st[blx];--i){
		if(a[i]+i>ed[blx])
			num[i]=1,pla[i]=a[i]+i;
		else	
			num[i]=num[i+a[i]]+1,pla[i]=pla[i+a[i]];
	}
	return;
}
int main(){
	n=get(),m=get();
    for(register int i=1;i<=n;++i)
        a[i]=get();
    build();//分块
	int op,p,q,ans=0;
    while(m--){
        op=get(),p=get();
        if(op==1){
			ask(p);
        	printf("%d %d\n",ans1,ans2);	//输出答案
		}
        	
		else
			q=get(),modify(p,q); 
	}
    return 0;
}