У меня зашло за O(Nlog^2N). Идея в том, что мы выбираем половину изменений, находим какие вершины они меняют. Делаем сжатие путей так, чтобы все прыжки вели в изменяемые вершины (и при этом всегда вели в первую изменяемую вершину на пути). После чего решаем задачу на изменяемых вершинах. Там тоже делим количество изменений пополам и.т.д. Квадрат логарифма вылезает из-за того, что после обработки изменений в рекурсивных вызовах, мне нужно "разжать" пути обратно. Таким образом я поддерживаю инвариант, что текущие сжатые дуги указывают на первую вершину в пути, которая попадает в текущее подмножество вершин. Для этого я после обработки изменений в рекурсивных вызовах просто рассчитываю все сжатые дуги для текущего подмножества заново за O(NlogN). Наверное это доводится до O(NlogN), но нужно реализовывать как-то аккуратнее.

Ссылка на решение: http://codeforces.com/contest/13/submission/13762281

Do you really think that problem E can be that easy? After updating the strength of the hole number X the answer will change not only for the hole X, but also for all holes Y_i from which X is reachable by 1 or more jumps. The number of such holes Y_i is O(N).

Well, to be more precise, we can say that there IS an optimal final sequence whose numbers are all from the original sequence, which can be proved by contradiction. Take the original sequence "3 1" for example. Although "2 2" is an optimal one whose numbers are not from the original sequence, "1 1" or "3 3" is optimal and their numbers are from the original one.

https://cp-algorithms.com/data_structures/sqrt_decomposition.html

And I've got a TLE on test 13.Anyone help me?

/*
ID: jerrywcy
LINK: http://codeforces.com/contest/13/problem/E
LANG: C++
STATUS:
*/
#include <bits/stdc++.h>

#define init(array,x) memset(array,x,sizeof(array))

using namespace std;

const int inf=0x3f3f3f3f;
const int maxn=100010;

int n,q;
int a[maxn];
int m,len;
int l[1010],r[1010];
int pos[maxn],nxt[maxn],step[maxn];

void build(){
	m=len=sqrt(n);
	for (int cur=1;cur<=m;cur++){
		l[cur]=len*(cur-1)+1;
		r[cur]=len*cur;
		for (int i=l[cur];i<=r[cur];i++){
			pos[i]=cur;
			int j=i;
			while (j<=r[cur] && j<=n){
				j=min(j+a[j],n+1);
				step[i]++;
			}
			nxt[i]=j;
		}
	}
	if (r[m]!=n){
		m++;
		l[m]=r[m-1]+1;
		r[m]=n;
		for (int i=l[m];i<=r[m];i++){
			pos[i]=m;
			int j=i;
			while (j<=r[m] && j<=n){
				j=min(j+a[j],n+1);
				step[i]++;
			}
			nxt[i]=j;
		}
	}
	return ;
}

void add(int x,int y){
	int bl=pos[x];
	a[x]=y;
	for (int i=x;i>=l[bl];i--){
		nxt[i]=max(nxt[i+a[i]],n+1),step[i]=step[i+a[i]]+1;
	}
	return ;
}

void query(int x){
	int cnt=0;
	while (nxt[x]<=n){
		cnt+=step[x];
		x=nxt[x];
	}
	while (x+a[x]<=n)x+=a[x],cnt++;
	printf("%d %d\n",x,cnt+1);
	return ;
}

void solve(){
	int opt;
	scanf("%d",&opt);
	if (!opt){
		int x,y;
		scanf("%d %d",&x,&y);
		add(x,y);
	}
	else{
		int x;
		scanf("%d",&x);
		query(x);
	}
}

int main()
{
	scanf("%d %d",&n,&q);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]);
	build();
	while (q--)solve();

	return 0;
}